耳切法简述

耳切法简述

将简单多边形分解成三角形称为多边形的三角剖分。对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)$。

1. 凸顶点列表 $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}$ 中。
   

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

   顶点 $4$ 的耳朵去掉，所以三角剖分中的第2个三角形$T_{2,4,5}$
   

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

   顶点 $5$ 的耳朵去掉，所以三角剖分中的第3个三角形$T_{2,5,6}$
   

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

   顶点 $6$ 的耳朵去掉，所以三角剖分中的第4个三角形$T_{2,6,7}$
   

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

   顶点 $9$ 的耳朵去掉，所以三角剖分中的第5个三角形$T_{0,8,9}$
   

6. 凸顶点的列表 $C=0,1,2,8$；
   反射顶点的列表 $R=7$；
   耳朵的列表 $E=0,2,8$，

   顶点 $0$ 的耳朵去掉，所以三角剖分中的第6个三角形$T_{0,1,8}$
   

7. 凸顶点的列表 $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);
}

相关链接

1. 多边形三角化
2. TriangulationByEarClipping.pdf