文档介绍：凸包&最近点对 ---zwh凸包?顾名思义,凸包就是把给定的点包围在内部的面积最小的凸多边形。?如图就是一个点集的凸包预备篇:点的排序与左转判定?点的排序?找给定点集的凸包,通常需要一些预处理过程,点的排序就是其中之一。?下面给出一种将点按照一定规则排序的方法,这个预处理过程在很多凸包寻找算法中都扮演重要角色?(通常取横坐标或纵坐标最小的点)?记为P0,如图:? 与其他点,分别计算这些线段与“竖直向下方向”的夹角,按照夹角?由小到达的顺序将各线段的另一端(一端是P0)标号为P1、P2、P3……如图:?(为了使图像更清晰,现擦去所有线段)?左转判定?这是经典的计算几何学问题,判断向量p1=(x1,y1)到p2=(x2,y2)是否做左转,只需要判断x1*y2-x2*y1 的正负,如果结果为正,则从p1 到p2 做左转。?矢量叉积?设有点p0(x0,y0),p1(x1,y1),p2(x2,y2).(p0p1),(p0p2)是共p0的两条向量,叉积d = (p0p1)x(p0p2) = (x1-x0)*(y2-y0) - (x2-x0)*(y1-y0)?叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:若d > 0 , 则(p0p1)在(p0p2)的顺时针方向。若d < 0 , 则(p0p1)在(p0p2)的逆时针方向。(图示方向)若d = 0 , 则(p0p1)与(p0p2)共线,但可能同向也可能反向。??相关博客http://blog./fivedoumi/article/details/7653128?1 点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。?2 一组平面上的点,求一个包含所有点的最小的凸多边形,这就是凸包问题了。这可以形象地想成这样:在地上放置一些不可移动的木桩,用一根绳子把他们尽量紧地圈起来,并且为凸边形,这就是凸包了Graham's Scan法求解凸包问题基本步骤:⒈在所有点中选取y坐标最小的一点P0。然后按照其它各点p和基点构成的向量<H,p>;与x轴的夹角进行排序,夹角由大至小进行顺时针扫描,反之则进行逆时针扫描。实现中无需求得夹角,只需根据向量的内积公式求出向量的模即可。,必须考虑到前面的线段是否会出现在凸包上。从基点开始,凸包上每条相临的线段的旋转方向应该一致,并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化,则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断,叉积为正(逆时针扫描判断是否为负),则将上一点删除。删除过程需要回溯,将之前所有叉积符号相反的点都删除,然后将新点加入凸包。按照上述步骤进行扫描,直到点集中所有的点都遍例完成,即得到凸包。模拟过程:?这是排序后的几个点准备堆栈(有线段相连的点表示在栈中的点)栈内元素:P0,P1,P2