[科普中国]-凸包

定义

⒈对于一个集合D，D中任意有限个点的凸组合的全体称为D的凸包。

⒉对于一个集合D，所有包含D的凸集之交称为D的凸包。

可以证明，上述两种定义是等价的

概念

1 点集Q的凸包（convex hull）是指一个最小凸多边形，满足Q中的点或者在多边形边上或者在其内。右图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

2 一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，并且为凸边形，这就是凸包了。

数学定义：设S为欧几里得空间 的任意子集。包含S的最小凸集称为S的凸包，记作conv(S)。1

平面求法常见求法凸包最常用的凸包算法是Graham扫描法和Jarvis步进法

Graham's Scan法这个算法是由数学大师葛立恒（Graham）发明的，他曾经是美国数学学会（AMS）主席、AT&T首席科学家以及国际杂技师协会（IJA）主席。

问题

给定平面上的二维点集，求解其凸包。

过程

⒈ 在所有点中选取y坐标最小的一点H，当作基点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。然后按照其它各点p和基点构成的向量；与x轴的夹角进行排序，夹角由大至小进行顺时针扫描，反之则进行逆时针扫描。实现中无需求得夹角，只需根据余弦定理求出向量夹角的余弦值即可。以下图为例，基点为H，根据夹角由小至大排序后依次为H，K，C，D，L，F，G，E，I，B，A，J。下面进行逆时针扫描。

⒉ 线段；一定在凸包上，接着加入C。假设线段；也在凸包上，因为就H，K，C三点而言，它们的凸包就是由此三点所组成。但是接下来加入D时会发现，线段；才会在凸包上，所以将线段；排除，C点不可能是凸包。

⒊ 即当加入一点时，必须考虑到前面的线段是否在凸包上。从基点开始，凸包上每条相临的线段的旋转方向应该一致，并与扫描的方向相反。如果发现新加的点使得新线段与上线段的旋转方向发生变化，则可判定上一点必然不在凸包上。实现时可用向量叉积进行判断，设新加入的点为，上一点为，再上一点为。顺时针扫描时，如果向量与的叉积为正（逆时针扫描判断是否为负），则将上一点删除。删除过程需要回溯，将之前所有叉积符号相反的点都删除，然后将新点加入凸包。

在上图中，加入K点时，由于线段要旋转到的角度，为顺时针旋转，所以C点不在凸包上，应该删除，保留K点。接着加入D点，由于线段要旋转到的角度，为逆时针旋转，故D点保留。按照上述步骤进行扫描，直到点集中所有的点都遍历完成，即得到凸包。

复杂度

这个算法可以直接在原数据上进行运算，因此空间复杂度为O⑴。但如果将凸包的结果存储到另一数组中，则可能在代码级别进行优化。由于在扫描凸包前要进行排序，因此时间复杂度至少为快速排序的O(nlgn)。后面的扫描过程复杂度为O(n)，因此整个算法的复杂度为O(nlgn)。

Jarvis步进法对于一个有三个或以上点的点集Q，过程如下：

计算点集最右边的点为凸包的顶点的起点，如上图的P3点。

Do

For i = 0 To 总顶点数

计算有向向量P3->Pi

If 其余顶点全部在有向向量P3->Pi的左侧或右侧，则Pi点为凸包的下一顶点

Pi点加入凸包列表

GoTo 1

End If

Next

Exit Do

1:

Loop

此过程执行后，点按极角自动顺时针或逆时针排序，只需要按任意两点的次序就可以了。而左侧或右侧的判断可以用前述的矢量点积性质实现。

中心法先构造一个中心点，然后将它与各点连接起来，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。

水平法从最左边的点开始，按斜率递增的方法，求出凸包上部；再按斜率递减的方法，求出凸包下部。水平法较中心法减少了斜率无限大的可能，减少了代码的复杂度。

快包法选择最左、最右、最上、最下的点，它们必组成一个凸四边形（或三角形）。这个四边形内的点必定不在凸包上。然后将其余的点按最接近的边分成四部分，再进行快包法(QuickHull)。

代码实例C代码一#include#include#includetypedefstruct{ doublex; doubley;}POINT;POINTresult[102];//保存凸包上的点，相当于所说的栈SPOINTa[102];intn,top;doubleDistance(POINTp1,POINTp2)//两点间的距离{ returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}doubleMultiply(POINTp1,POINTp2,POINTp3)//叉积{ return((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));}intCompare(constvoid*p1,constvoid*p2)//根据p0->p1的极值和p0->p2的极值进行比较，如果极值相同则用距离长度比较{ POINT*p3,*p4; doublem; p3=(POINT*)p1; p4=(POINT*)p2; m=Multiply(a[0],*p3,*p4); if(m