3D Convex Hull

3D Convex Hull

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

為了方便儲存,凸多邊形剖分成數個三角形。

為了方便儲存,多點共面剖分成數個三角形。

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

p = {{5,4,8},{1,8,6},{6,6,4},{9,6,4},{7,9,7},{6,9,9},{8,0,8},{1,5,4},{1,1,5},{6,6,3},{8,6,7},{0,1,6},{9,7,10},{7,6,3},{6,2,7},{10,4,4},{5,8,2},{8,3,2},{2,6,3},{0,0,1},{7,3,3},{6,9,8},{2,8,1},{10,6,10},{5,8,10},{8,2,4},{5,7,6},{6,7,2},{1,10,1},{0,4,5},{1,3,2},{8,1,0},{4,10,2},{1,9,0},{6,3,5},{9,1,3},{8,10,1},{9,6,8},{6,2,3},{10,0,2},{8,1,10},{10,2,4},{9,0,10},{2,9,6},{10,5,10},{4,0,5},{2,3,8},{3,8,4},{3,3,10},{4,5,1}};

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

Facet

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

為了方便儲存,刻面從凸多邊形變成三角形。

3D Convex Hull: Graham's Scan

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

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

3D Convex Hull: Gift Wrapping Algorithm

演算法

http://www.cs.jhu.edu/~misha/Spring20/09.pdf

找到第一個凸包刻面:座標最低的三個點。

以邊為軸,旋轉的掃描面,尋找最外圍的點,包覆成新刻面。

當凸包多點共面,在掃描面上尋找二維凸包、尋找三角剖分。

時間複雜度O(FNlogN),F是凸包刻面數量。多面體最多有O(N)個面,時間複雜度可寫作O(N²logN)。

3D Convex Hull: Monotone DAG

Monotone Chain可以推廣成Monotone DAG嗎?

等你發表論文。

3D Convex Hull: Incremental Method

演算法

逐次增加一點,更新刻面。

運用刻面法向量,判斷刻面屬於凸面、凹面、切面。

運用刻面有向邊,找到凹切分際。

保留凸面與切面,移除凹面,添加當前輸入點到凹切分際的新刻面。如此便完成了新凸包。

預先按照XYZ座標排序所有點(平移的掃描面),就能保證當前輸入點都在凸包外部,就能保留多點共面的三角剖分。

時間複雜度O(N²)。加速為O(NlogN)至今仍是懸案。

UVa 11769 12513 ICPC 5090 4795

3D Convex Hull: Divide-and-Conquer Method

演算法

所有點分成左右兩堆,分別求凸包。合併兩個凸包,用滾動的。時間複雜度O(NlogN)。

http://www.cs.jhu.edu/~misha/Spring20/10.pdf

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

3D Convex Hull: Quick Hull Algorithm

演算法

時間複雜度O(N²)。實務上最快的演算法。

http://media.steampowered.com/apps/valve/2014/DirkGregorius_ImplementingQuickHull.pdf