凸包 (Convex Hull)

引言：“橡皮筋”类比

在木板上随意钉上一堆钉子。现在，拿一根橡皮筋撑开，套住所有的钉子，然后松手让它紧紧崩住。 橡皮筋形成的形状就是 凸包 (Convex Hull)。它是包围所有点的最外层边界。

在机器人技术、图形学和图像处理中，高效地找到这个边界至关重要。Graham 扫描法 通过按角度排序点，并进行一次扫描来构建凸包。

算法要解决什么问题？

• 输入： 一组 2D 点。
• 输出： 构成最外层多边形的点的子集。
• 承诺： 将成千上万个点的云团简化为一个简单的多边形边界。

核心思想 (直觉版)

1. 从低处开始： 找到最底部的点（它一定是凸包的一部分）。
2. 按角度排序： 根据其他所有点与起始点的夹角进行排序。
3. 行走与转向： 遍历排序后的点。
   • 如果我们向 左转，继续前进。
   • 如果我们向 右转（形成了一个凹陷），说明前一个点其实在凸包内部，而不是在边界上。移除 前一个点。

典型业务场景

• ✅ 碰撞检测： 在游戏中，与其检测与复杂的 10,000 面体角色模型的碰撞，不如先检测与其简单的凸包的碰撞。
• ✅ 机器人： 机器人需要知道一组障碍物周围的“安全区域”以规划路径。
• ✅ 图像处理： 手势识别通常涉及找到手部形状的凸包来数手指（凸包上的凹陷）。
• ✅ GIS (地图)： “找出覆盖这 50 个送货地点的区域范围。”

性能与复杂度总结

• 时间： $O(N \log N)$（主要耗时在排序上）。
• 空间： $O(N)$。

小结：一句话记住它

“凸包是几何学的‘保鲜膜’。它将复杂的数据点云简化为干净、凸出的边界，使得碰撞和面积等计算变得极快。”