二维凸包算法详解：从历史到现代

"这篇文章除了介绍二维凸包的概念，还探讨了其在计算几何中的重要性，并简述了预处理步骤，如点的排序和左转判定。文章通过历史脉络，介绍了1972年斯卡兰斯奇提出的‘三硬币’算法作为求凸包的开创性方法。" 二维凸包算法是计算几何领域中的一个重要问题，它涉及到从一组点中找到一个最小的点集，这些点可以连接成一个凸多边形，覆盖原始点集的所有点。这个问题有多种实际应用，比如在图形学中构建最小包围边界，或者在路径规划中找到最短路径等。 预处理是二维凸包算法的关键步骤。首先，我们需要找到一个确定会在凸包上的点，通常是横坐标或纵坐标最小的点，标记为P0。接着，将其他点与P0相连，计算它们与竖直方向的夹角，并按角度从小到大进行排序，依次标记为P1、P2、P3等。这个排序对于后续算法的执行至关重要。 左转判定是计算几何中的基础工具，用于判断两个向量是否形成了一个左转角度。给定两个点P1(x1, y1)和P2(x2, y2)，可以通过计算向量p1到p2的叉积x1*y2 - x2*y1来判断。如果结果为正，表示从P1到P2是左转；若为负，则为右转；若为零，表示两向量平行。 1972年的“三硬币”算法由Sklansky提出，是二维凸包算法的早期经典方法。该算法利用点的排序，模拟硬币的旋转，不断更新“后”、“中”、“前”三个点的位置，直到所有点都被包含在内。当三枚硬币按“后-中-前”的顺序构成左转时，硬币“后”移动到“前”的位置，更新三个硬币的标识。如果三枚硬币不构成左转，那么硬币“中”移到“后”的位置，移除原先的“后”。这个过程持续进行，直至找到最终的凸包。 这只是二维凸包算法的一种实现，随着时间的发展，计算几何学家们提出了许多其他高效算法，如 Gift Wrapping（ Jarvis march）算法、 Graham's Scan 和 QuickHull 等。这些算法各有特点，适用于不同的场景，但它们的核心思想都是通过点的顺序和方向判断来逐步构建凸包。 理解二维凸包算法不仅有助于深入计算几何，还能为编程竞赛、图形学和路径规划等领域提供理论基础。学习这些算法不仅需要掌握数学知识，还需要对数据结构和算法有深入的理解，以便在实践中选择最适合的方法。