前言

學習過了多邊形的一些相關內容，總算可以開始學習凸包了。

這篇博客主要介紹如何在給出的點集中求出凸包。

關于凸包面積可以參考初學計算幾何（三）——多邊形的簡單操作中的多邊形面積的求法。

排序

求凸包的第一步便是將點集按照這個方法進行排序：

inline bool operator < (Vector A,Vector B) {return fabs(A.x-B.x)>eps?A.x<B.x:A.y<B.y;}

這應該還是比較好理解的吧，就是以\(x\)坐標為第一關鍵字，以\(y\)坐標為第二關鍵字進行排序。

接下來的步驟

顯然，排完序后得到的第一個點和最后一個點肯定在凸包內。

每次要加入一個新的點，如果已加入點數大于\(1\)，我們將當前點\(p\)與最后加入的點\(S_n\)比較，如果\(\vec{S_{n-1},S_n}\)不在\(\vec{S_{n-1},p}\)左邊，我們就可以將\(S_n\)彈出。

不斷重復該過程，直到無法繼續彈出了，我們再將點\(p\)加入凸包中。

然后倒著執行一遍類似的操作即可。

具體實現見代碼：

inline ConvexHull GetConvexHull(Polygon S) {register int i,t;register ConvexHull res;for(sort(S.p+1,S.p+S.n+1),i=1;i<=S.n;++i)//先排一遍序{while(res.n>1&&dcmp(Cro(res.p[res.n]-res.p[res.n-1],S.p[i]-res.p[res.n-1]))<=0) --res.n;//將不滿足條件的點彈出res.p[++res.n]=S.p[i];//將當前點加入凸包中}for(t=res.n,i=S.n-1;i;--i)//倒著執行一遍類似的操作{while(res.n>t&&dcmp(Cro(res.p[res.n]-res.p[res.n-1],S.p[i]-res.p[res.n-1]))<=0) --res.n;res.p[++res.n]=S.p[i];}return res; }

后記

關于如何求凸包的內容大致就是這些吧。

個人認為還是比較好理解的。

這里有一道例題：【UVA10652】Board Wrapping。

轉載于:https://www.cnblogs.com/chenxiaoran666/p/ConvexHull.html

總結

以上是生活随笔為你收集整理的初学计算几何（四）——初识凸包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。