最小凸包算法

求最小凸包

——Graham算法——凸包概念凸包（ConvexHull）是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。

这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会主席，AT&T首席科学家以及国际杂技师协会主席。Graham算法是在某种意义上来说求解二维静态凸包的一种最优的算法，这种算法目前被广泛的应用于对各种以二维静态凸包为基础的ACM题目的求解。Graham算法的时间复杂度大约是nlogn,因此在求解二维平面上多个点构成的凸包时，消耗时间相对较少。Graham_scan算法1.在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。Graham_scan算法H2.然后按照其它各点p和基点构成的向量<H,p>与x轴的夹角进行排序，夹角由小到大进行逆时针扫描。并依次排序。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p53.将P0,P1,p2放入栈中。并将栈内的点依次排号并命名为Ai（i以0为起点）,P0,P1必为凸包的两点Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p53.以P1为基点，判断P1P2P3是否为逆时针方向，若是，P3进栈。再A2以为基点，判断A2A3P4。Graham_scan算法H（P0）p10p8p9p7p6p4p3p2p1p14p13p12p11p0p1p2A0A1A2p3A3p53.以A2为基点，判断A2A3P4是否为逆时针方向，若是，P4进栈,若不是，P3出栈，P4进栈。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P4（进）A3p5（出栈）（入栈）P3（出）3.继续以A2为基点，判断A2A3P5是否为逆时针方向。若是，P5进栈，若不是，P4出栈，P5进栈。Graham_scan算法H（P0）p10p8p9p7p6P4P3p2p1p14p13p12p11p0p1p2A0A1A2P5（进栈）A3P5P4(出栈)3.继续以A2为基点，判断A2A3P6,可知A2A3P6为逆时针方向，故A6进栈。Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4（保存）（进栈）4.以A3为基点，判断A3A4P7,按照前面的方法，可得保存P6，P7进栈；Graham_scan算法H（P0）p10p8p9p7P6(保存)P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p7A55.按照此方法，可得栈中的点依次为：Graham_scan算法H（P0）p10p8p9p7P6P4P3p2p1p14p13p12p11p0p1p2A0A1A2p5A3P5p6A4p10A5p11p12p14A6A7A8几何中心算法H（P0）p10p8p9p7P6P4P