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

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

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

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

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

演算法

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

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

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

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

monotone chain可以推廣成monotone DAG嗎？

等你發表論文。

演算法

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

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

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

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

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

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

// 凸包的頂點 struct Point {float x, y, z;} p[10]; Point operator-(Point a, Point b) { return (Point){a.x - b.x, a.y - b.y, a.z - b.z}; } double dot(Point a, Point b) { return a.x * b.x + a.y * b.y + a.z * b.z; } Point cross(Point a, Point b) { return (Point){a.y * b.z - b.y * a.z, a.z * b.x - b.z * a.x, a.x * b.y - b.x * a.y}; } bool zero(Point a) { return a.x == 0 && a.y == 0 && a.z == 0; } bool cmp(Point a, Point b) { if (a.x != b.x) return a.x < b.x; if (a.y != b.y) return a.y < b.y; return a.z < b.z; } // 凸包的刻面 // 一個刻面為三個頂點（索引值），逆時針順序為向外。 struct Facet {int a, b, c;}; Point normal(Facet f) { return cross(p[f.b] - p[f.a], p[f.c] - p[f.a]); } // 凸包的刻面的有向邊 // 一條有向邊為兩個頂點（索引值） int vis[10][10]; void convex_hull() { // 預先排序 sort(p, p+10, cmp); /* 必須弄出一個四面體。 */ // 四面體頂點（索引值） int v0, v1, v2, v3; // 指定第一點 v0 = 0; // 令前兩點不共點 int i = 0; for (++i; i<10; ++i) if (!zero(p[i] - p[v0])) { v1 = i; break; } if (i == 10) return; // 通通共點 // 令前三點不共線 for (++i; i<10; ++i) if (!zero(cross(p[v1] - p[v0], p[i] - p[v0]))) { v2 = i; break; } if (i == 10) return; // 通通共線 // 令前四點不共面 Point n = cross(p[v1] - p[v0], p[v2] - p[v0]); float d = 0; for (++i; i<10; ++i) if ((d = dot(n, p[i] - p[v0])) != 0) { v3 = i; break; } if (i == 10) return; // 通通共面 /* 開始建立凸包 */ // 前四點形成的凸包 vector<Facet> cur; if (d > 0) { cur.push_back((Facet){v1,v0,v2}); cur.push_back((Facet){v0,v1,v3}); cur.push_back((Facet){v1,v2,v3}); cur.push_back((Facet){v2,v0,v3}); } else { cur.push_back((Facet){v0,v1,v2}); cur.push_back((Facet){v1,v0,v3}); cur.push_back((Facet){v2,v1,v3}); cur.push_back((Facet){v0,v2,v3}); } // 處理其餘點 for (int i=0; i<10; ++i) { if (i == v0 || i == v1 || i == v2 || i == v3) continue; vector<Facet> next; // 保留凸面與切面、移除凹面 for (int j=0; j<cur.size(); ++j) { Facet& f = cur[j]; // 保留凸面與切面 double d = dot(p[f.a] - p[i], normal(f)); if (d >= 0) next.push_back(f); // 刻面有向邊，記錄凸面、凹面、切面。 int side = 0; // 切面 if (d > 0) side = +1; // 凸面 if (d < 0) side = -1; // 凹面 vis[f.a][f.b] = side; vis[f.b][f.c] = side; vis[f.c][f.a] = side; } // 添加當前輸入點到凹凸分際的新刻面 for (int j=0; j<cur.size(); ++j) { Facet& f = cur[j]; int a = f.a, b = f.b, c = f.c; // 找到凹面，分別觀察三條邊，判斷是否為凹凸分際。 if (vis[a][b] < 0 && vis[a][b] != vis[b][a]) next.push_back((Facet){a, b, i}); if (vis[b][c] < 0 && vis[b][c] != vis[c][b]) next.push_back((Facet){b, c, i}); if (vis[c][a] < 0 && vis[c][a] != vis[a][c]) next.push_back((Facet){c, a, i}); } cur = next; } }

UVa 11769 12513 ICPC 5090 4795

演算法

所有點分成左右兩堆，分別求凸包。合併兩個凸包，用滾動的。筷子串起兩個凸包，放在地上滾，以筷子為軸轉一圈。

時間複雜度O(NlogN)。

演算法

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