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

平面凸包 ：

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

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

一、??Graham掃描法，運(yùn)行時(shí)間為O(nlgn)。

二、??Jarvis步進(jìn)法，運(yùn)行時(shí)間為O(nh),h為凸包中的頂點(diǎn)數(shù)。

1 問題描述1： 2 求覆蓋平面上n 個點(diǎn)的最小的凸多邊形。也可以這樣描述：給定一個連接的多邊形，可能是凸多邊形，也有可能是凹多邊形。現(xiàn)在，你的任務(wù)就是編程求這個多邊形的最小凸包。如果它本身是凸多邊形，那么最小凸包就是它本身。 3 數(shù)據(jù)范圍： 4 多邊形頂點(diǎn)坐標(biāo)X，Y 是非負(fù)整數(shù)，不超過512。 5 輸入： 6 共有K 組數(shù)據(jù)，每組測試數(shù)據(jù)的點(diǎn)都是按逆時(shí)針順序輸入的，沒有3 個點(diǎn)共線。 7 每組測試數(shù)據(jù)的第1 行是N，表示有N 個點(diǎn)。以下N 行，每行兩個整數(shù)X，Y。 8 輸出： 9 輸出格式與輸入格式一樣，第一行是K，表示共有K 組輸出。以下K 組數(shù)據(jù)： 10 每組的第一行為M，表示該凸包上有M 個頂點(diǎn)，以下M 行每行兩個整數(shù)X，Y，表示凸包頂點(diǎn)的坐標(biāo)。也按逆時(shí)針方向輸出。 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掃描法

???基本思想：通過設(shè)置一個關(guān)于候選點(diǎn)的堆棧s來解決凸包問題。

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

注：下列過程要求|Q|>=3，它調(diào)用函數(shù)TOP（S）返回處于堆棧S?頂部的點(diǎn)，并調(diào)用函數(shù)NEXT-TO?–TOP（S）返回處于堆棧頂部下面的那個點(diǎn)。但不改變堆棧的結(jié)構(gòu)。

GRAHAM-SCAN(Q)

1???????????設(shè)P0?是Q?中Y?坐標(biāo)最小的點(diǎn)，如果有多個這樣的點(diǎn)則取最左邊的點(diǎn)作為P0；

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

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

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

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

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

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

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

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

10????????return S

?

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

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

舉例如下：

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

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

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

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

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

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

練習(xí)：HDU 1392 Surround the Trees

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

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

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。