耳切法简述

将简单多边形分解成三角形称为多边形的三角剖分。对n个顶点的简单多边形的任何三角剖分都有n-2个三角形。其中最简单的算法，称为耳切法（EarClipping）。

耳的定义

多边形的一个 “耳” 是由 $V_{i_{0}}$ 、 $V_{i_{1}}$ 和 $V_{i_{2}}$ 三个连续顶点形成的三角形，其中 $V_{i_{1}}$ 是一个凸顶点，该顶点的内角小于π弧度，从 $V_{i_{0}}$ 到 $V_{i_{2}}$ 的线段完全位于多边形内部，该三角形内部除自身顶点外无其他多边形顶点。线段< $V_{i_{0}}$ , $V_{i_{2}}$ >称为多边形的对角线。顶点 $V_{i_{1}}$ 称为耳尖。

算法步骤

第一步是将多边形存储为双向链表，以便可以快速删除耳尖。构建此列表是一个 $O (n)$ 过程。
第二步是迭代顶点并找到耳朵。对于每个顶点和相应的三角形，测试所有其他顶点，看看是否有任何顶点在三角形内部；如果没有一个在里面，就有耳朵。如果至少有一个在里面，就没有耳朵。实际上，在三角形测试中只考虑反射顶点就足够了。反射顶点是由共享它的两条边形成的内角大于 π 弧度的顶点。

多边形的数据结构使用数组同时维护四个双链表进行存储，而不是在标准列表数据结构中动态分配和释放内存。
多边形的顶点存储在循环列表 $L$ 中，凸顶点存储在线性列表 $C$ 中，反射顶点存储在线性列表 $R$ 中，耳尖存储在循环列表 $E$ 中。
图一简单多边形

上图的简单多边形，其顶点位置为：
$V_{0}=(3,48), V_{1}=(52,8), V_{2}=(99,50), V_{3}=(138,25), V_{4}=(175,77), V_{5}=(131,72), V_{6}=(111,113), V_{7}=(72,43), V_{8}=(26,55), V_{9}=(29,100)$ 。

凸顶点列表 $C = 0, 1, 3, 4, 6, 9$ ；
反射顶点的初始列表 $R = 2, 5, 7, 8$ ；
耳朵的列表 $E = 3, 4, 6, 9$ ，

顶点 $3$ 的耳朵去掉，所以三角剖分中的第1个三角形 $T_{2,3,4}$
注意：顶点 $8$ 在三角形 $T_{9,0,1}$ 中，顶点 $7$ 在三角形 $T_{0,1,2}$ 中。
凸顶点的列表 $C = 0, 1, 4, 6, 9$ ；
反射顶点的列表 $R = 2, 5, 7, 8$ ；
耳朵的列表 $E = 4, 6, 9$ ，

顶点 $4$ 的耳朵去掉，所以三角剖分中的第2个三角形 $T_{2,4,5}$
凸顶点的列表 $C = 0, 1, 5, 6, 9$ ；
反射顶点的列表 $R = 2, 7, 8$ ；
耳朵的列表 $E = 5, 6, 9$ ，

顶点 $5$ 的耳朵去掉，所以三角剖分中的第3个三角形 $T_{2,5,6}$
凸顶点的初始列表 $C = 0, 1, 2, 6, 9$ ；
反射顶点的初始列表 $R = 7, 8$ ；
耳朵的列表 $E = 6, 9$ ，

顶点 $6$ 的耳朵去掉，所以三角剖分中的第4个三角形 $T_{2,6,7}$
凸顶点的列表 $C = 0, 1, 2, 9$ ；
反射顶点的列表 $R = 7, 8$ ；
耳朵的列表 $E = 9, 2$ ，

顶点 $9$ 的耳朵去掉，所以三角剖分中的第5个三角形 $T_{0,8,9}$
凸顶点的列表 $C = 0, 1, 2, 8$ ；
反射顶点的列表 $R = 7$ ；
耳朵的列表 $E = 0, 2, 8$ ，

顶点 $0$ 的耳朵去掉，所以三角剖分中的第6个三角形 $T_{0,1,8}$
凸顶点的列表 $C = 1, 2, 8$ ；
反射顶点的列表 $R = 7$ ；
耳朵的列表 $E = 2, 8$ ，

顶点 $2$ 的耳朵去掉，所以三角剖分中的第7个三角形 $T_{1,2,7}$ ，同时最后一个三角形 $T_{1,7,8}$

8. 剖分后的三角列表

$T_{2,3,4}$ ， $T_{2,4,5}$ ， $T_{2,5,6}$ ， $T_{2,6,7}$ ， $T_{0,8,9}$ ， $T_{0,1,8}$ ， $T_{1,2,7}$ ， $T_{1,7,8}$

代码示例

虚幻引擎的实现源码：UE\Engine\Source\Runtime\GeometryCore\Private\CompGeom\PolygonTriangulation.cpp

//
// Triangulate using ear clipping
// This is based on the 3D triangulation code from MeshDescription.cpp, simplified for 2D polygons
// 
template<typename T>
void PolygonTriangulation::TriangulateSimplePolygon(const TArray<TVector2<T>>& VertexPositions, TArray<FIndex3i>& OutTriangles, bool bOrientAsHoleFill)
{struct Local{static inline bool IsTriangleFlipped(T OrientationSign, const TVector2<T>& VertexPositionA, const TVector2<T>& VertexPositionB, const TVector2<T>& VertexPositionC){T TriSignedArea = TTriangle2<T>::SignedArea(VertexPositionA, VertexPositionB, VertexPositionC);return TriSignedArea * OrientationSign < 0;}};OutTriangles.Reset();// Polygon must have at least three vertices/edges, or result is emptyint32 PolygonVertexCount = VertexPositions.Num();if (PolygonVertexCount < 3){return;}// compute signed area of polygondouble PolySignedArea2 = 0;for (int i = 0; i < PolygonVertexCount; ++i){const TVector2<T>& v1 = VertexPositions[i];const TVector2<T>& v2 = VertexPositions[(i + 1) % PolygonVertexCount];PolySignedArea2 += v1.X*v2.Y - v1.Y*v2.X;}bool bIsClockwise = PolySignedArea2 < 0;T OrientationSign = (bIsClockwise) ? -T(1) : T(1);// If perimeter has 3 vertices, just copy content of perimeter out if (PolygonVertexCount == 3){OutTriangles.Add(bOrientAsHoleFill ? FIndex3i(0, 2, 1) : FIndex3i(0, 1, 2));return;}// Make a simple linked list array of the previous and next vertex numbers, for each vertex number// in the polygon.  This will just save us having to iterate later on.TArray<int32> PrevVertexNumbers, NextVertexNumbers;PrevVertexNumbers.SetNumUninitialized(PolygonVertexCount, false);NextVertexNumbers.SetNumUninitialized(PolygonVertexCount, false);for (int32 VertexNumber = 0; VertexNumber < PolygonVertexCount; ++VertexNumber){PrevVertexNumbers[VertexNumber] = VertexNumber - 1;NextVertexNumbers[VertexNumber] = VertexNumber + 1;}PrevVertexNumbers[0] = PolygonVertexCount - 1;NextVertexNumbers[PolygonVertexCount - 1] = 0;int32 EarVertexNumber = 0;int32 EarTestCount = 0;for (int32 RemainingVertexCount = PolygonVertexCount; RemainingVertexCount >= 3; ){bool bIsEar = true;// If we're down to only a triangle, just treat it as an ear.  Also, if we've tried every possible candidate// vertex looking for an ear, go ahead and just treat the current vertex as an ear.  This can happen when // vertices are collinear or other degenerate cases.if (RemainingVertexCount > 3 && EarTestCount < RemainingVertexCount){const TVector2<T>& PrevVertexPosition = VertexPositions[PrevVertexNumbers[EarVertexNumber]];const TVector2<T>& EarVertexPosition = VertexPositions[EarVertexNumber];const TVector2<T>& NextVertexPosition = VertexPositions[NextVertexNumbers[EarVertexNumber]];// Figure out whether the potential ear triangle is facing the same direction as the polygon// itself.  If it's facing the opposite direction, then we're dealing with a concave triangle// and we'll skip it for now.if (!Local::IsTriangleFlipped(OrientationSign, PrevVertexPosition, EarVertexPosition, NextVertexPosition)){int32 TestVertexNumber = NextVertexNumbers[NextVertexNumbers[EarVertexNumber]];do{// Test every other remaining vertex to make sure that it doesn't lie inside our potential ear// triangle.  If we find a vertex that's inside the triangle, then it cannot actually be an ear.const TVector2<T>& TestVertexPosition = VertexPositions[TestVertexNumber];if (TTriangle2<T>::IsInside(PrevVertexPosition, EarVertexPosition, NextVertexPosition, TestVertexPosition)){bIsEar = false;break;}TestVertexNumber = NextVertexNumbers[TestVertexNumber];} while (TestVertexNumber != PrevVertexNumbers[EarVertexNumber]);}else{bIsEar = false;}}if (bIsEar){// OK, we found an ear!  Let's save this triangle in our output buffer.{int32 A = PrevVertexNumbers[EarVertexNumber], B = EarVertexNumber, C = NextVertexNumbers[EarVertexNumber];OutTriangles.Add(bOrientAsHoleFill ? FIndex3i(A, C, B) : FIndex3i(A, B, C));}// Update our linked list.  We're effectively cutting off the ear by pointing the ear vertex's neighbors to// point at their next sequential neighbor, and reducing the remaining vertex count by one.{NextVertexNumbers[PrevVertexNumbers[EarVertexNumber]] = NextVertexNumbers[EarVertexNumber];PrevVertexNumbers[NextVertexNumbers[EarVertexNumber]] = PrevVertexNumbers[EarVertexNumber];--RemainingVertexCount;}// Move on to the previous vertex in the list, now that this vertex was cutEarVertexNumber = PrevVertexNumbers[EarVertexNumber];EarTestCount = 0;}else{// The vertex is not the ear vertex, because it formed a triangle that either had a normal which pointed in the opposite direction// of the polygon, or at least one of the other polygon vertices was found to be inside the triangle.  Move on to the next vertex.EarVertexNumber = NextVertexNumbers[EarVertexNumber];// Keep track of how many ear vertices we've tested, so that if we exhaust all remaining vertices, we can// fall back to clipping the triangle and adding it to our mesh anyway.  This is important for degenerate cases.++EarTestCount;}}check(OutTriangles.Num() > 0);
}

耳切法简述