简单多边形的耳切三角剖分

形式陈述

一个凹简单多边形能否像剥洋葱一样，每次切下一块三角形，直到只剩最后一块？设输入 $P=(v_0,\ldots,v_{n-1})$ 逆时针、无孔、无零边、相邻边不重叠。主说明先取无三点共线的一般位置，之后再说明共线边界。

当前边界的连续三个顶点 $a,b,c$ 构成一个耳，是指 $b$ 为严格凸顶点， $ac$ 为内部对角线，且三角形 $abc$ 的内部不含其他当前顶点。删除 $b$ 、用 $ac$ 代替 $ab,bc$ ，同时输出三角形 $abc$ 。剩余边界仍是一个较小的简单多边形。

在一般位置下，可以先检查

\operatorname{orient}(a,b,c)>0,

再检查其余顶点没有落入耳三角形。这个局部凸性和空三角形测试保证 $ac$ 合法：若别的边穿入三角形又穿出，它不能穿过原多边形的 $ab,bc$ ，也不能用一条直线段两次穿过 $ac$ ；因而会在三角形内留下顶点，与空性矛盾。

初始为每个顶点计算耳标记，放入候选队列。每切掉一个耳，只重新检查它的两个相邻顶点，其余顶点的相邻三元组没有改变。这里还需一个几何引理：若凸顶点的候选三角形含其他边界顶点，它必含一个凹顶点。其他边界只能经候选底边进入这个三角形；取其中朝耳尖伸得最深的一段边界，其最高凸出点对这个凹口是凸角，对原多边形则是凹角，因此给出所需顶点。被删的耳尖是凸顶点，不会删掉这个凹顶点阻挡证书。所以非邻接的旧非耳仍被阻挡；旧耳也不会因为删除一个外部顶点而失效。只有与被删耳尖相邻的两个三元组需要重新检查。使用双向循环链表保存边界，可在 $O(1)$ 时间完成删除和找到两侧邻居。

每次耳测试扫描至多 $n$ 个顶点。初始 $n$ 次，之后每次删除至多两次，所以总时间 $O(n^2)$ ，空间 $O(n)$ ，另加输出的 $n-2$ 个三角形。若每轮重新扫描所有顶点并对每个候选扫描全部其他顶点，则是更慢的直接实现，不能把它称作同一份 $O(n^2)$ 实现。

直觉

凸角只说明边界在这里向内转得合适，耳还要求这块三角形没有盖住别的边界。凹口可能从远处伸进来，所以“看起来尖尖的一角”不一定能切。

为什么算法不会卡住？先有一个基本事实：每个至少四边的简单多边形都有内部对角线。可取一个凸角 $abc$ ；若其三角形空，取 $ac$ ；否则在三角形内选择朝 $b$ 方向最高的顶点，用空的三角形帽区域证明它能与 $b$ 连成内部对角线。沿对角线递归便得到三角剖分。

任一不加新顶点的剖分有 $n-2$ 个三角形、 $n-3$ 条内部对角线，其三角形邻接图连通，边数比顶点数少一，因此是树。当 $n\ge4$ 时，这棵树至少有两个顶点，因而至少有两片叶；这两片叶三角形只通过一条对角线连接其他三角形，各自另外两条边就在原边界上，所以给出两个耳，这就是双耳定理。对每次删除后较小的多边形重复这个论证，保证至少还有一个可切耳。

同一十边形中一个凸角因三角形包含远处顶点而不是耳；真正的耳可切下并留下简单边界 — 凸角与合法耳的区别

例子与边界

使用下列十边形，编号严格按所列顺序：

\begin{array}{c|rrrrrrrrrr} i&0&1&2&3&4&5&6&7&8&9\\\hline x_i&0&8&8&6&6&4&4&2&2&0\\ y_i&0&0&6&6&2&2&5&5&6&6 \end{array}

$v_0$ 是凸顶点，但三角形 $(v_9,v_0,v_1)$ 含有 $v_5=(4,2)$ ，所以不能切掉 $v_0$ 。真正可以先切的是 $(v_1,v_2,v_3)$ 。删去 $v_2$ 后，新的连续三元组 $(v_1,v_3,v_4)$ 又成为耳。

一份完整输出为

(1,2,3),(1,3,4),(0,1,4),(0,4,5), (9,0,5),(5,6,7),(9,5,7),(7,8,9).

共有八个三角形。每片按逆时针方向排列，面积均为正，面积和等于原多边形面积 $38$ 。边计数也能独立核验：每条原边出现一次，每条内部对角线出现两次，而且两次方向相反。只检查面积和不够，因为重叠与缺口可能彼此抵消；合法对角线、方向与边计数要一起检查。

这个输入含非相邻共线点。核验程序采用保守测试：只有严格凸顶点可切，任何其他顶点落在候选三角形的闭区域中都阻挡该耳，因此不会产生穿过别的顶点的对角线。若输入含相邻共线顶点，可以在预处理删除不改变轮廓的中间点，记录映射；若任务要求保留每个原顶点，则需在相关三角形边上重新插入它们并细分，不能还使用删点后的 $n$ 来报告三角形数。

自交、带孔和零宽连接不满足简单无孔合约。带孔区域先连桥再耳切需要新的边界表示与弱简单性处理；任意连一条桥可能穿过障碍。点集的Delaunay 剖分也不能替代这里的算法，因为它可能填满凹口。

推论与应用

不变量是“已经输出的三角形内部两两不交；它们与当前剩余多边形恰好覆盖原区域”。每切下一耳，公共部分只有新对角线，因而保持不变量；最后剩一三角形，得到覆盖整个区域的剖分。方向判定既判断凸性，也核验三角形包含和边相交，必须采用一致的精确符号。

耳切的实现短，适合作为更快算法的独立参照。大输入可改用单调划分后进行线性栈剖分；两种输出对角线不必相同，但都必须通过上述覆盖与计数检查。最终剖分还给漏斗最短路提供三角形通道。

参考资料

Joseph O’Rourke，Computational Geometry in C，第 2 版，1998，Chapter 1，尤其 Code 1.14。作者的代码与勘误索引确认耳切代码的位置；该索引列出三角剖分实现与对应章节。
Mark de Berg 等，Computational Geometry: Algorithms and Applications，第 3 版，2008，§3.1，课程原书，对角线、三角形计数与剖分结构。
Dave Mount，Polygon Triangulation，2026，pp.1–2，三角剖分与对偶树。

形式陈述 ​

反向链接

形式陈述