计算几何：详解凸包算法及实现

"这篇学习笔记主要探讨了计算几何中的基础概念——凸包，并提供了相关的算法实现，包括如何判断点在凸包内的位置以及如何求解凸包。" 在计算几何中，凸包(Convex Hull)是指包含一组点的最小凸多边形，这些点的所有连线都在多边形内部或边界上。凸包对于很多应用都非常重要，如路径规划、机器学习、图像处理等。学习计算几何的基础，理解凸包的概念和算法是必不可少的。 这里提到了两种常见的凸包算法： Graham扫描法 和 Jarvis步进法 ，这两种方法都是用于求解二维平面上的点集的凸包。 1. **Graham扫描法**： - 首先，找到点集中最低的点（按y坐标排序，如果y相同则按x坐标排序），然后将其他点按照相对于这个最低点的角度进行排序。 - 接着，创建一个空栈`qs`，将最低点入栈。 - 对于排序后的每个点，如果它与栈顶两个点形成的向量叉积大于0，说明新点在当前凸包的边界上，将其入栈。否则，需要不断地弹出栈顶元素，直到满足条件为止。这样就构建了下凸包。 - 然后，从最后一个点开始逆序遍历，重复上述过程，构建上凸包。 - 最终，栈`qs`中保存的就是不含重复点的凸包。 2. **Jarvis步进法（Gift Wrapping Algorithm）**： - 选择一个极点（通常是最低的点），然后从这个点开始，对其他点进行遍历。 - 对每个点，检查它与当前凸包上的最近点（极点到点的向量与凸包上某边的向量之间的叉积）形成的角度，如果角度大于0，则这个点在凸包上，将这个点加入凸包。 - 继续遍历，直到回到起点，得到的路径就是凸包的边界。 此外，笔记中还提供了判断点是否在凸包内的函数`contain`，它通过计算点与多边形边的叉积来确定点的位置。如果点在多边形内部，叉积之和为偶数；如果在边上，为奇数；如果在外部，为零。此方法基于射线交叉次数判定规则。 在实际编程实现时，需要注意边界情况和效率优化，例如，对于`convexHullNonStrict`函数，可能需要处理严格凸包和非严格凸包的区别，以及处理重复点的情况。 总结来说，这篇学习笔记详细介绍了计算几何中的凸包问题，包括理论概念、判断点在凸包内的方法以及两种常用的求解凸包的算法。对于深入理解和应用计算几何，这些都是非常关键的知识点。