本节介绍了用于查找一组点的凸包的有效几何算法。计算几何是研究几何问题的算法。它广泛应用于计算机图形、游戏、模式识别、图像处理、机器人、地理信息系统以及计算机辅助设计和制造。部分提出了一种用于查找最接近的点对的几何算法。本节介绍寻找凸包的几何算法。
给定一组点，凸包是包围所有这些点的最小凸多边形，如下图（a）所示。如果连接两个顶点的每条线都在多边形内部，则多边形是凸多边形。例如，下图(a)中的顶点v0、v1、v2、v3、v4和v5形成凸多边形，但下图(b)中则不然，因为连接v3和v1的线不在多边形内部.
凸包在游戏编程、模式识别和图像处理中有很多应用。在介绍算法之前，使用交互式工具来熟悉这个概念会很有帮助，如下图（c）所示。该工具允许您添加和删除点并动态显示凸包。
已经开发了许多算法来寻找凸包。本节介绍两种流行的算法：礼物包装算法和格雷厄姆算法。
礼物包装算法
一种直观的方法，称为礼物包装算法，其工作原理如下：
- 第1步：给定一个点列表S，让S中的点标记为s0，s1，...，sk。选择最右边的最低点S。如下图(a)所示，h0就是这样一个点。将 h0 添加到列表 H 中。（H 最初是空的。算法完成后，H 将保存凸包中的所有点。）令 t0 为 h0。
- 第2步：设t1为s0。对于S中的每个点p，如果p位于从t0到t1的直线的右侧，则令t1为p。 （经过第2步，从t0到t1的直线右侧不再有任何点，如下图（b）所示。）
- 步骤3：如果t1为h0（见下图（d）），则H中的点构成S的凸包。否则，将t1添加到H中，令t0为t1，然后返回步骤2（见下图） (c)).
凸包逐渐扩展。在步骤 2 之后，没有点位于从 t0 到 t1 的直线的右侧，这一事实支持了正确性。这确保了 S 中具有两个点的每条线段都落在多边形内。
在步骤 1 中找到最右边的最低点可以在 O(n) 时间内完成。可以在 O(1) 时间内确定一个点是在线的左侧、右侧还是在线上。因此，在步骤 2 中找到新点 t1 需要 O(n) 时间。步骤 2 重复 h 次，其中 h 是凸包的大小。因此，该算法需要 O(hn) 时间。在最坏的情况下，h 是 n。
格雷厄姆算法
Ronald Graham 于 1972 年开发了一种更高效的算法，如下步骤所示。
第1步：给定一个点列表S，选择最右边的最低点并将其命名为p0。如下图(a)所示，p0就是这样一个点。
步骤2：以p0为中心，沿x轴对S中的点进行角度排序，如下图(b)所示。如果存在平局并且两个点具有相同的角度，则丢弃更接近 p0 的点。 S 中的点现在排序为 p0、p1、p2、...、pn-1。
步骤3：将p0、p1、p2压入堆栈H。（算法结束后，H包含凸包中的所有点。）
第4步：
i = 3;
而（我
设 t1 和 t2 分别为栈 H 中顶部的第一个和第二个元素；
if (pi 位于从 t2 到 t1 的直线的左侧) {
将 pi 推入 H；
我++; // 考虑 S 中的下一点。
}
其他
将顶部元素弹出堆栈 H.
}
第5步：H中的点形成凸包。
凸包是逐步发现的。最初，p0、p1 和 p2 形成凸包。考虑p3。 p3 位于当前凸包之外，因为点按其角度的升序排序。如果p3严格位于p1到p2连线的左侧（见下图（c）），则将p3推入H。现在p0、p1、p2和p3形成凸包。如果p3在p1到p2连线的右侧（见下图（d）），则将p2从H中弹出，将p3压入H中。现在p0、p1和p3形成凸包，p2在H的内部这个凸包。你可以通过归纳证明，第5步中H中的所有点对于输入列表S中的所有点形成一个凸包。
在步骤 1 中找到最右边的最低点可以在 O(n) 时间内完成。可以使用三角函数计算角度。但是，您可以对点进行排序，而无需实际计算它们的角度。观察到当且仅当 p2 位于从 p0 到 p1 的线的左侧时，p2 才会形成比 p1 更大的角度。可以在 O(1) 时间内确定一个点是否在线的左侧。使用合并排序或堆排序算法可以在 O(n log n) 时间内完成步骤 2 中的排序。步骤 4 可以在 O(n) 时间内完成。因此，该算法需要 O(n logn) 时间。
