3D Convex Hull(Under Construction!)

3D Convex Hull

三維凸包的表面,由數個凸多邊形拼成。

為了方便儲存,凸多邊形習慣剖分成數個三角形。三維凸包的表面,由數個三角形拼成。

我們習慣以逆時針順序記錄三角形的三個頂點(三角形的三條邊變成有向邊)。這麼做的好處是,三角形依序取兩條邊計算叉積,就得到朝外的法向量。

Facet

高維度空間的物體,一塊平坦表面稱作「刻面」,就好像被刻了一刀。鑽石就是刻面的極致工藝。

三維凸包的繞行順序是什麼?

二維凸包的頂點,是以時針順序繞行一圈。三維凸包的頂點,至今仍未發現適當的繞行順序;三維的Graham's Scan至今仍是懸案。

UVa 12513

3D Convex Hull: Enumeration(Under Construction!)

窮舉所有三角形,嘗試作為凸包刻面。凸包刻面外部必無點;所有點必在凸包刻面內部、或者與凸包刻面共面。時間複雜度O(N⁴)。

此演算法並不完美。如果凸包表面有多點共面,則會得到多餘的三角形。

3D Convex Hull: Gift Wrapping Algorithm(Under Construction!)

先找到第一個凸包刻面,找座標最低的三個點,O(N)。

接下來不斷尋找位於最外側的點,最外側的點與目前的刻面連線(也就是包覆)形成新刻面。

時間複雜度是O(NF),其中F為凸包刻面數量。多面體最多有O(N)個面,因此F可寫作O(N),時間複雜度可寫作O(N²)。

3D Convex Hull: Incremental Method(Under Construction!)

與2D版本概念相同。通常採用試誤法,窮舉刻面,容易實作。時間複雜度是O(N²)。

運用刻面法向量,可以輕鬆判斷刻面屬於凸面、凹面、切面。留下凸面與切面、移除凹面,然後增加當前輸入點到凹凸分際的新刻面,就完成了凸包。

利用三角形有向邊的概念,可以輕鬆記錄凹凸分際的哪些邊已經製作過新刻面。這是一個很好用的實作技巧。

UVa 11769 ICPC 5090 4795

3D Convex Hull: Divide and Conquer(Under Construction!)

與二維版本相同,總時間複雜度是O(NlogN)。

比較困難的地方是合併兩個三維凸包,O(N)。

3D Convex Hull: Chan's Algorithm

非常優美的演算法。

https://cs.uwaterloo.ca/~tmchan/ch3d/ch3d.pdf

[1999 Basch et al]
往 xy-plane ,也就是底面,沿負z軸方向投影,量出與 z=ax+by+c 平面之間的距離

當b是正值,
正前方是一個往上的斜坡,
各種不同遠近、與xz平面平行的豎立平面,整片沿著斜坡朝自己滑下來,疊在xz平面上。

Erdős-Szekeres Conjecture

Erdős-Szekeres Conjecture(Happy Ending Problem)

http://garden.irmacs.sfu.ca/?q=op/erdos_szekeres_conjecture

平面上任意2ᴺ + 1個頂點(不會多點共線),是否能描出一個有N+2個頂點的凸多邊形。例如任意三個點可以描出凸三角形,任意五個點可以描出凸四邊形,任意九個點可以描出凸五邊形,以此類推。

Szekeres發表了這個猜想之後,有一位女數學家證明了N更大的情形,兩人因而相知相遇、結為連理,有了幸福快樂的結局。因此Erdős暱稱此猜想為Happy Ending Problem。

註:Erdős-Szekeres Theorem是另外一件事情,與Erdős-Szekeres Conjecture不同。

2^N個數字,任何一種排列,
必能形成長度為N+1的「先遞增、再遞減子序列」。

這個命題曾經用來證明此猜想,不過結果是失敗的。

目前來說,凹與凸是無法量化的,凹與凸無法全體一起比較、全體一起排序。即便是凸包演算法,也只能局部逐一判斷凹凸。

用長度來衡量凹凸乍看是個不錯的點子,不過困難重重,可能不是一個好方向。

最後附上此命題的證明。

2^(N-2)個數字,任何一種排列,
必能形成長度為N-1的「先遞增、再遞減子序列」。

數學歸納法。

當N=2時,一個數字的任何一種排列,
都可以形成一個長度為1的「先遞增、再遞減子序列」。

當N=3時,兩個數字的任何一種排列,
都可以形成一個長度為2的「先遞增、再遞減子序列」。
例如12,剛好都是遞增。
例如21,剛好都是遞減。
例如11,說是遞增或是遞減都可以。

假設N=k時成立。
則N=k+1時,
我們將2^(k-1)個數字的隨便一個排列,中間切一刀,等分為左半和右半。
左半、右半各自都可以形成長度為k-1的「先遞增、再遞減子序列」。

左半「先遞增、再遞減子序列」的最後一個數字,叫做p,
右半「先遞增、再遞減子序列」的第一個數字,叫做q,
如果p > q,則左半與q可形成長度為k的「先遞增、再遞減子序列」。
如果p < q,則p與右半可形成長度為k的「先遞增、再遞減子序列」。
如果p = q,則上述兩種情形任意一種皆可。
得證。

Erdős-Nagy Theorem

一個凹多邊形不斷翻折,最後必能變成凸多邊形。

http://www.matrix67.com/blog/archives/4780