凸包（Convexhull）

目录

什么是凸包

在了解凸包之前，须先认识何谓“凸多边形”(ConvexPolygon)。从直观上说，一个凸多边形就是没有任何凹陷位的多边形。我们在低年级数学所学习的三角形、正方形、长方形、平行四边形、正五边形、正六边形等等，都是凸多边形的例子。但是以下这个“凸”字形却并非凸多边形，因为箭头指着的地方实际是一个凹陷位。

可是上述这一定义很不严密，究竟何谓“凹陷位”？实在难以说清楚。因此在数学上，凸多边形有另一个严格的定义。假设我们在一个多边形上(包括多边形的边界及边界围封的范围)任意取两点并以一条线段连结该两点，如果线段上的每一点均在该多边形上，那么我们便说这个多边形是凸的。根据以上定义，我们便可判断“凸”字形的确不是凸的。例如，在下图中，连结A、B两点的线段有一部分并不在该多边形上。

认识了凸多边形后，我们便可了解何谓凸包。给定平面上的一个(有限)点集(即一组点)，这个点集的凸包就是包含点集中所有点的最小面积的凸多边形。例如，下图的点集共包含9个点，图中的六边形便是该点集的凸包。其中构成六边形的6个点称为“凸包上的点”(HullPoint)，其余3个点则并非“凸包上的点”。请注意上述定义中“最小面积”这个限制条件，因为除了凸包以外，还有无限多个包含点集中所有点的凸多边形。例如，只要画一个面积足够大的四边形，便可包围任意给定的点集。因此假如没有这个限制条件，求凸包就变成非常容易但却没有唯一解的运算。

凸包的表达方式

在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。

X的凸包可以用X内所有点()的线性组合来构造。

它的缺点是不能推广到二维以上的情况。

单调链

将点按x坐标的值排列，再按y坐标的值排列。

选择x坐标为最小值的点，在这些点中找出y坐标的值最大和y坐标的值最小的点。对于x坐标为最大值也是这样处理。将两组点中y坐标值较小的点连起。在这条线段下的点，找出它们之中y坐标值最大的点，又在它们之间找x坐标值再最小和最大的点……如此类推。

时间复杂度是O(nlogn)。

分治法

将点集X分成两个不相交子集。求得两者的凸包后，计算这两个凸包的凸包，该凸包就是X的凸包。时间复杂度是O(nlogn)。

快包法(Akl-Toussaint启发式)

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