最小凸包算法.pptx

求最小凸包——Graham算法——凸包概念 凸包（Convex Hull）是一个计算几何（图形学）中的概念。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。 Graham_scan算法 这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会主席，ATT首席科学家以及国际杂技师协会主席。 Graham 算法是在某种意义上来说求解二维静态凸包的一种最优的算法，这种算法目前被广泛的应用于对各种以二维静态凸包为基础的ACM题目的求解。Graham算法的时间复杂度大约是nlogn,因此在求解二维平面上多个点构成的凸包时，消耗时间相对较少。Graham_scan算法1. 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。HGraham_scan算法2.然后按照其它各点p和基点构成的向量H,p与x轴的夹角进行排序，夹角由小到大进行逆时针扫描。并依次排序。p11p10p6p12p8p5p7p4p9p14p13p3p2p1H（P0）Graham_scan算法3.将P0, P1, p2放入栈中。并将栈内的点依次排号并命名为Ai（i以0为起点）, P0, P1必为凸包的两点p11p10p6p12p8p5p7p4p9p14p13p3p2p2p1A2p1A1H（P0）p0A0Graham_scan算法3.以P1为基点，判断 P1P2P3是否为逆时针方向，若是，P3进栈。再A2以为基点，判断A2A3P4。p11p10p6p12p8p7p5p4p9p14p13p3p2p3A3p1p2A2H（P0）p1A1p0A0Graham_scan算法3.以A2为基点，判断 A2A3P4是否为逆时针方向，若是，P4进栈,若不是，P3出栈，P4进栈。p11p10p6p12p8p7p5P4（入栈）p9p14p13（出栈）P3p2P3（出）P4（进）A3p1p2A2H（P0）p1A1p0A0Graham_scan算法3.继续以A2为基点，判断A2A3P5是否为逆时针方向。若是，P5进栈，若不是，P4出栈，P5进栈。p11p10p6p12p8p7P5P4p9p14p13P3P4(出栈)p2P5（进栈）A3p1p2A2H（P0）p1A1p0A0Graham_scan算法3.继续以A2为基点，判断A2A3P6,可知A2A3P6为逆时针方向，故A6进栈。p11p10（进栈）P6p12p8p7P5（保存）P4p9p14p13p6P3A4p2p5A3p1p2A2H（P0）p1A1p0A0Graham_scan算法4. 以A3为基点，判断A3A4P7,按照前面的方法，可得保存P6，P7进栈；p11p10P6(保存)p12p8p7P5P4p9p14p13p7A5p6P3A4p2p5A3p1p2A2H（P0）p1A1p0A0Graham_scan算法5.按照此方法，可得栈中的点依次为：p11p10P6p12p8p14p7P5A8p12A7P4p11p9A6p14p10p13A5p6A4P3p5p2A3p2p1A2p1H（P0）A1p0A0几何中心算法 凸包几何中心即凸包重心，由于该凸包质量分布均匀，故凸包几何中心的X,Y坐标即为最小凸包点X,Y坐标的的平均值。p11p10P6p12p8p7P5P4p9p14p13P3p2p1H（P0）谢谢！