如何設計演算法計算三維空間中n個點的凸包表面積？

輸入n個點的坐標，輸出表面積。

如果逐面枚舉判斷在不在表面的話，時間複雜度O（n4）這效率也太低了吧。

平面凸包有較好用的演算法O（nlogn），如果是空間的話又該如何優化呢？

---

是有這麼個演算法來著，不過比平面凸包複雜不少，原理也是步進。注意凸包的每個面要麼是三角形面，要麼可以分割成三角形面。

在演算法過程中，我們維護兩個集合：集合S，是最後凸包頂點的集合；集合E，是最後凸包邊的集合。如果像這個問題中一樣，要計算表面積，那麼再加上一個集合F，是最後凸包三角形面的集合，合計三個集合。

跟平面的情況一樣，首先找到某個坐標分量（比如說z分量）最小的點，它一定在凸包上。從這一點開始，像包包裹一樣，找出這個凸包。我們首先將這個點放進S里。

找一個跟這一點的連線，與xy平面成的角最小的點，這可以通過與z軸正方向單位向量做內積，然後除以向量長度的方法來比較（可以兩邊同時平方來消除根號，提高精度和速度）。這個點也一定是凸包上的點，而且跟第一個點相鄰。這兩個點的連線一定在凸包上。

如果z分量最小的點有許多個，按平面凸包的方式找到凸包上的一條邊，從這裡開始。

把這條邊加入E。從這兩個點的連線開始：

由於這條邊位於凸包上，一定存在一個過這條邊的平面，使得其他點都在這個平面的單側，利用這個特性，我們可以給其他點排序，比較兩個點的時候，計算這四個點組成的有向四面體的體積（方法是減去基準點的坐標之後，計算三個向量的行列式值），結果為正，則第一個點大於第二個點，為負則第一個點小於第二個點。這樣就跟平面凸包的情況下一樣，將剩下的點按照與這條邊的正方向成的角度排好了序。這個排好序的兩側的點一定都在凸包里，把這兩個點找出來，加入到凸包集合S里；它也可能是已經在集合S里的點。如果這兩個三角形面不在F中，把它加到F中（累加表面積）。

考慮兩個三角形面的另外四條邊，如果它們不在E中，則將它們加入到E中，然後遞歸執行上一個過程。注意跟平面凸包的步進不同，平面凸包每次都會找到唯一的下一步，而三維凸包則需要一個遞歸、回溯的過程；但是凸包上每條邊只會被處理一次。這個過程類似於圖的DFS。

如果有多個頂點共面，這個問題會比較tricky，比較簡單的方法是如果最大值（或者最小值）有多個頂點，則在這多個頂點上進行平面凸包的計算（比如使用步進法），然後將這個凸包上所有頂點都加入到S中，將凸包上所有的邊都加入到E中，將凸包分解成三角形加入到F中。雖然面的分解不唯一，但邊是唯一的。接下來對所有的之前不在E中的邊，遞歸執行之前的步驟。

複雜度上，凸包每條棱最多被處理一次，每次處理複雜度是O(n)。根據歐拉定律，有，對於三角形面的多面體，有，因此有，所以最終的複雜度是O(mn)，其中m是凸包上頂點的個數；最壞情況下是O(n^2)。

---

推薦閱讀：