《求凸包算法详解》由会员分享，可在线阅读，更多相关《求凸包算法详解（3页珍藏版）》请在金锄头文库上搜索。
1、概念凸包(Con vex Hull )是一个计算几何(图形学)中的概念。用不严谨的话来讲，给定二维平面上 的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有点的。严谨的定 义和相关概念参见维基百科：凸包。这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会(AMS)主席、AT&T首 席科学家以及国际杂技师协会(IJA)主席。(太汗了，这位大牛还会玩杂技)问题给定平面上的二维点集，求解其凸包。过程1.在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则 选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量H
2、,p 与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需 求得夹角，只需根据向量的内积公式求出向量的模即可。以下图为例，基点为H,根据夹角由小 至大排序后依次为H, K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。2. 线段vH, K定在凸包上，接着加入C。假设线段vK, C也在凸包上，因为就H, K，C 三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段vK, D才会 在凸包上，所以将线段vK, C排除，C点不可能是凸包。3. 即当加入一点时，必须考虑到前面的线段是否会出现在凸包上。从基点开始，凸包上每条相 临的线段的旋转方
3、向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的 旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断，设新加入 的点为pn + ，上一点为pn，再上一点为pn -。顺时针扫描时，如果向量pn - H pn与卩十Pn+ 1 的叉积为正(逆时针扫描判断是否为负)，则将上一点删除。删除过程需要回溯，将之前所 有叉积符号相反的点都删除，然后将新点加入凸包。在上图中，加入K点时，由于线段VH,K相对于H,C为顺时针旋转，所以C点不在凸包上, 应该删除，保留K点。接着加入D点，由于线段VK, D相对VH, K为逆时针旋转，故D点 保留。按照上述步骤进行扫描，直到点集中所有的点都遍例完成，即得到凸包。复杂度这个算法可以直接在原数据上进行运算，因此空间复杂度为0(1)。但如果将凸包的结果存储到 另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少 为快速排序的0(nlgn)。后面的扫描过程复杂度为0(n),因此整个算法的复杂度为0(nlgn)。
