最小凸包算法

求最小凸包

——Graham算法——凸包概念凸包（ConvexHull）是一個計算幾何（圖形學(xué)）中的概念。用不嚴(yán)謹(jǐn)?shù)脑拋碇v，給定二維平面上的點(diǎn)集，凸包就是將最外層的點(diǎn)連接起來構(gòu)成的凸多邊型，它能包含點(diǎn)集中所有點(diǎn)的。

這個算法是由數(shù)學(xué)大師葛立恒(Graham)發(fā)明的，他曾經(jīng)是美國數(shù)學(xué)學(xué)會主席，AT&T首席科學(xué)家以及國際雜技師協(xié)會主席。Graham算法是在某種意義上來說求解二維靜態(tài)凸包的一種最優(yōu)的算法，這種算法目前被廣泛的應(yīng)用于對各種以二維靜態(tài)凸包為基礎(chǔ)的ACM題目的求解。Graham算法的時間復(fù)雜度大約是nlogn,因此在求解二維平面上多個點(diǎn)構(gòu)成的凸包時，消耗時間相對較少。Graham_scan算法1.在所有點(diǎn)中選取y坐標(biāo)最小的一點(diǎn)H，當(dāng)作基點(diǎn)。如果存在多個點(diǎn)的y坐標(biāo)都為最小值，則選取x坐標(biāo)最小的一點(diǎn)。坐標(biāo)相同的點(diǎn)應(yīng)排除。Graham_scan算法H2.然后按照其它各點(diǎn)p和基點(diǎn)構(gòu)成的向量<H,p>與x軸的夾角進(jìn)行排序，夾角由小到大進(jìn)行逆時針掃描。并依次排序。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p53.將P0,P1,p2放入棧中。并將棧內(nèi)的點(diǎn)依次排號并命名為Ai（i以0為起點(diǎn)）,P0,P1必為凸包的兩點(diǎn)Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p53.以P1為基點(diǎn)，判斷P1P2P3是否為逆時針方向，若是，P3進(jìn)棧。再A2以為基點(diǎn)，判斷A2A3P4。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p3A3p53.以A2為基點(diǎn)，判斷A2A3P4是否為逆時針方向，若是，P4進(jìn)棧,若不是，P3出棧，P4進(jìn)棧。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P4（進(jìn)）A3p5（出棧）（入棧）P3（出）3.繼續(xù)以A2為基點(diǎn)，判斷A2A3P5是否為逆時針方向。若是，P5進(jìn)棧，若不是，P4出棧，P5進(jìn)棧。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P5（進(jìn)棧）A3P5P4(出棧)3.繼續(xù)以A2為基點(diǎn)，判斷A2A3P6,可知A2A3P6為逆時針方向，故A6進(jìn)棧。Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4（保存）（進(jìn)棧）4.以A3為基點(diǎn)，判斷A3A4P7,按照前面的方法，可得保存P6，P7進(jìn)棧；Graham_scan算法H（P0）p10p8p9p7P6(保存)P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p7A55.按照此方法，可得棧中的點(diǎn)依次為：Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p10A5p11p12p14A6A7A8幾何中心算法H（P0）p10p8p9p7P6P4P