耳切法简述

将简单多边形分解成三角形称为多边形的三角剖分。对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 empty
	int32 PolygonVertexCount = VertexPositions.Num();
	if (PolygonVertexCount < 3)
	{
		return;
	}


	// compute signed area of polygon
	double 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 cut
			EarVertexNumber = 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);
}