在學習了一些有關計算機幾何的基礎知識和一些基本工具之后要快速的解決一些簡單的幾何問題，如兩點之間的距離、兩線段的交點個數等等是可以輕松應付的，但是對于復雜點的幾何問題，我們還是要有更好的算法，這樣才可以更高效的解決它。在這一篇中來總結 平面凸包 的 Graham算法；http://www.cnblogs.com/jbelial/

平面凸包 ：

?定義： 對一個簡單多邊形來說，如果給定其邊界上或內部的任意兩個點，連接這兩個點的線段上的所有點都被包含在該多邊形的邊界上或內部的話，則該多邊形為凸多邊形 。

在解決平面凸包下面介紹了兩種算法：

一、??Graham掃描法，運行時間為O(nlgn)。

二、??Jarvis步進法，運行時間為O(nh),h為凸包中的頂點數。

1 問題描述1： 2 求覆蓋平面上n 個點的最小的凸多邊形。也可以這樣描述：給定一個連接的多邊形，可能是凸多邊形，也有可能是凹多邊形。現在，你的任務就是編程求這個多邊形的最小凸包。如果它本身是凸多邊形，那么最小凸包就是它本身。 3 數據范圍： 4 多邊形頂點坐標X，Y 是非負整數，不超過512。 5 輸入： 6 共有K 組數據，每組測試數據的點都是按逆時針順序輸入的，沒有3 個點共線。 7 每組測試數據的第1 行是N，表示有N 個點。以下N 行，每行兩個整數X，Y。 8 輸出： 9 輸出格式與輸入格式一樣，第一行是K，表示共有K 組輸出。以下K 組數據： 10 每組的第一行為M，表示該凸包上有M 個頂點，以下M 行每行兩個整數X，Y，表示凸包頂點的坐標。也按逆時針方向輸出。 11 樣例輸入： 12 1 13 14 14 30 30 15 50 60 16 60 20 17 70 45 18 86 39 19 112 60 20 200 113 21 250 50 22 300 200 23 130 240 24 76 150 25 47 76 26 36 40 27 33 35 28 樣例輸出： 29 1 30 8 31 60 20 32 250 50 33 300 200 34 130 240 35 76 150 36 47 76 37 30 30

?????????????????????????????????????????????????????????????????????????????????????????????????????????????

Graham掃描法

???基本思想：通過設置一個關于候選點的堆棧s來解決凸包問題。

???操作：輸入集合Q中的每一個點都被壓入棧一次，非CH（Q）(表示Q的凸包)中的頂點的點最終將被彈出堆棧，當算法終止時，堆棧S中僅包含CH(Q)中的頂點，其順序為個各頂點在邊界上出現的逆時針方向排列的順序。

注：下列過程要求|Q|>=3，它調用函數TOP（S）返回處于堆棧S?頂部的點，并調用函數NEXT-TO?–TOP（S）返回處于堆棧頂部下面的那個點。但不改變堆棧的結構。

GRAHAM-SCAN(Q)

1???????????設P0?是Q?中Y?坐標最小的點，如果有多個這樣的點則取最左邊的點作為P0；

2???????????設<P1,P2,……,Pm>是Q?中剩余的點，對其按逆時針方向相對P0?的極角進行排序，如果有數個點有相同的極角，則去掉其余的點，只留下一個與P0?距離最遠的那個點；

3???????????PUSH(p0 , S)

4???????????PUSH(p1 , S)

5???????????PUSH(p3 , S)

6???????????for i?←?3 to m

7???????????????do while?由點NEXT-TOP-TOP（S），TOP（S）和Pi?所形成的角形成一次非左轉

8???????????????????do POP(S)

9???????????????PUSH(pi , S)

10????????return S

?

首先，找一個凸包上的點，把這個點放到第一個點的位置P0。然后把P1~Pm?按照P0Pi的方向排序，可以用矢量積(叉積)判定。

做好了預處理后開始對堆棧中的點<p3,p4,...,pm>中的每一個點進行迭代，在第7到8行的while循環把發現不是凸包中的頂點的點從堆棧中移去。（原理：沿逆時針方向通過凸包時，在每個頂點處應該向左轉。因此，while循環每次發現在一個頂點處沒有向左轉時，就把該頂點從堆棧中彈出。）當算法向點pi推進、在已經彈出所有非左轉的頂點后，就把pi壓入堆棧中。

舉例如下：

????????????????????????????

??????????????????????????????????

????????????????????????????

?????????????????????????????????

??????????????????????????????????

?????????????????????????????????????????????????????????

練習：HDU 1392 Surround the Trees

模板：http://www.cnblogs.com/jbelial/archive/2011/08/05/2128624.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的计算几何-经典算法-凸包的全部內容，希望文章能夠幫你解決所遇到的問題。

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