数学大学
B. Extreme Points
计算几何 · 01. Convex Hull
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
B. Extreme Points
计算几何 · 01. Convex Hull
Extremity
极点：不属于任何「其他三点构成的三角形」的点——凸包顶点的代数刻画。
定义
若点不在其余点任一三角形的内部或边界上，则为极点
地位
极点恰好组成凸包的全部顶点
Strategy
朴素策略：逐点检查是否极点，每个点对其余点的所有三角形做包含测试。
复杂度
n 个点 × C(n−1,3) 个三角形，O(n⁴)
意义
正确但慢，作为算法优化的起点基线
In-Triangle Test
点在三角形内测试：点同时处于三条边的同一内侧即在内。
判据
对三条边分别做同侧检验，三次全过即在内
To-Left Test
ToLeft 测试：用叉积判断点在有向线的左侧还是右侧，几何判定的原子操作。
计算
两点与待测点组成的行列式符号
零的特殊性
叉积为零即共线，需单独约定归属
Determinant
ToLeft 测试的落点是一个 3×3 行列式：几何判定化为代数计算。
行列式
三行分别为 [1 x y] 的三点行列式
正负含义
正为左侧，负为右侧，零为共线
本节要点
- ✓极点 = 不落在任何别的三角形内
- ✓朴素策略 O(n⁴) 只作基线
- ✓ToLeft 测试用 3×3 行列式实现
延伸主题：实现 ToLeft 函数统计一个点集的极点数
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1ToLeft 测试为什么被称为计算几何的「原子操作」？
参考答案几乎一切几何判定——点在三角形内、两线段是否相交、凸包转向——都能分解为若干次 ToLeft 测试。它把几何直觉压缩成一次行列式计算，精度与效率的关键都集中在这一个函数里。
2ToLeft 测试用行列式实现，浮点误差会带来什么问题？
参考答案坐标大或共线附近的点，行列式值可能在浮点误差内翻转符号，导致极点误判。对策：整数坐标用精确整数运算，浮点坐标引入误差阈值 ε 做容差判定。
3为什么「极点不在任何三角形内」等价于「是凸包顶点」？
参考答案非极点必然落在点集的凸包内部或边上，而凸包可被其余点的三角形剖分覆盖，故必落在某个三角形内；反之凸包顶点在任何由其他点构成的三角形之外。两个刻画互为充要。