最小凸包算法

1、 凸包（Convex Hull）是一個(gè)計(jì)算幾何（圖形學(xué)）中的概念。用不嚴(yán)謹(jǐn)?shù)脑拋?lái)講，給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來(lái)構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有點(diǎn)的。 這個(gè)算法是由數(shù)學(xué)大師葛立恒(Graham)發(fā)明的，他曾經(jīng)是美國(guó)數(shù)學(xué)學(xué)會(huì)主席，AT&T首席科學(xué)家以及國(guó)際雜技師協(xié)會(huì)主席。 Graham 算法是在某種意義上來(lái)說(shuō)求解二維靜態(tài)凸包的一種最優(yōu)的算法，這種算法目前被廣泛的應(yīng)用于對(duì)各種以二維靜態(tài)凸包為基礎(chǔ)的ACM題目的求解。Graham算法的時(shí)間復(fù)雜度大約是nlogn,因此在求解二維平面上多個(gè)點(diǎn)構(gòu)成的凸包時(shí)，消耗時(shí)間相對(duì)較少。1. 在所有點(diǎn)中選取y坐標(biāo)最小的一點(diǎn)H，當(dāng)作基點(diǎn)。

2、如果存在多個(gè)點(diǎn)的y坐標(biāo)都為最小值，則選取x坐標(biāo)最小的一點(diǎn)。坐標(biāo)相同的點(diǎn)應(yīng)排除。H H2.然后按照其它各點(diǎn)p和基點(diǎn)構(gòu)成的向量與x軸的夾角進(jìn)行排序，夾角由小到大進(jìn)行逆時(shí)針掃描。并依次排序。H H（P P0 0）p10p8p9p7p6p4p3p2p1p14p13p12p11p53.將P0, P1, p2放入棧中。并將棧內(nèi)的點(diǎn)依次排號(hào)并命名為Ai（i以0為起點(diǎn)）, P0, P1必為凸包的兩點(diǎn)H H（P P0 0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p53.以P1為基點(diǎn)，判斷 P1P2P3是否為逆時(shí)針?lè)较?，若是，P3進(jìn)棧。再A2以為基點(diǎn)，判斷A2A3P4

3、。H H（P P0 0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p3A3p53.以A2為基點(diǎn)，判斷 A2A3P4是否為逆時(shí)針?lè)较颍羰?，P4進(jìn)棧,若不是，P3出棧，P4進(jìn)棧。H H（P P0 0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P4（進(jìn)）A3p5（出棧）（入棧）P3（出）3.繼續(xù)以A2為基點(diǎn)，判斷A2A3P5是否為逆時(shí)針?lè)较?。若是，P5進(jìn)棧，若不是，P4出棧，P5進(jìn)棧。H H（P P0 0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P5（進(jìn)棧）A3P5

4、P4(出棧)3.繼續(xù)以A2為基點(diǎn)，判斷A2A3P6,可知A2A3P6為逆時(shí)針?lè)较?，故A6進(jìn)棧。H H（P P0 0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4（保存）（進(jìn)棧）4. 以A3為基點(diǎn)，判斷A3A4P7,按照前面的方法，可得保存P6，P7進(jìn)棧；H H（P P0 0）p10p8p9p7P6(保存)P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p7A55.按照此方法，可得棧中的點(diǎn)依次為：H H（P P0 0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p10A5p11p12p14A6A7A8H H（P P0 0）p10p8p9p7P6P4P3p2p1p14p