数学大学
A. Convexity
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
A. Convexity
计算几何 · 01. Convex Hull
Why Convex Hull
凸包是计算几何的基石：一堆点「撑开」的最小凸区域，大量问题在它上面化简。
定义
包住所有点的最小凸多边形
地位
最近点对、直径、碰撞检测的预处理步骤
Nails In The Table
钉子与橡皮筋直觉：板上的钉子被橡皮筋套住收紧，露在外围的钉子就是凸包顶点。
橡皮筋模型
收紧后贴住的钉子集合即凸包
内部点
被围在内部的点不属于凸包顶点
Paint Blending
调色的凸组合直觉：两种颜料混合出的颜色落在两色连线上。
凸组合
系数非负且和为一的线性组合
混合封闭
凸集内任两点的凸组合仍在集内
Color Space
色彩空间的凸性：可显示颜色集合通常是凸的，混合不会跑出色域。
色域
三原色可达的颜色集合
凸性意义
凸色域保证中间色调都能显示
本节要点
- ✓凸包：包住所有点的最小凸区域
- ✓橡皮筋直觉识别顶点
- ✓凸组合封闭是凸性的代数定义
延伸主题：实现一个凸包算法思考色域为何设计成凸
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么很多几何问题「先求凸包再算」会更快？
参考答案最远点对、最小包围圆等问题的解只会出现在凸包顶点上——内部点可以整体剔除。凸包把点集规模从 n 压到 h（通常很小），后续算法在 h 上跑自然更快。
2凸包的「最小」体现在哪两个方向？
参考答案两层含义：作为凸集，它是包含全部点的所有凸集合中面积（或体积）最小的；作为多边形，它的顶点是原点集的子集。两者合起来定义了唯一确定的凸包。
3判断一个点是否在凸包上，有什么 O(n) 的在线方法？
参考答案维护当前凸包，对每个新点逐一检查它在不在任何一条边的左侧（或右侧）。不在任何边同侧即新顶点，需要更新凸包结构；在线增量法正是这种思路的实现。