三角形剖分是通过沿着轮廓的边往前走（walking the edges of the contour）来完成的，对于每组三个顶点，确定是否可以形成有效的内部三角形。从所有潜在的候选者中，选择具有最短的新边（译注：即下图中的虚线）的那个。新边被称为“分割边”（partition edges），或简称为“分割”（partition）。该过程继续处理剩余的顶点，直到三角形剖分完成。
这个算法可能有点难以描述。所以这里有一些例子。首先看一个有效分割边的例子。对于顶点 A、B 和 C，其中 AB 是潜在的分割边…
原文
This algorithm can be a little difficult to describe. So here are some examples. First, a valid partition. For the vertices A, B, and C, where AB is the potential partition...
沿着连接到顶点 A 的边打出两条射线。内角是多边形方向上的角。 如果分割边的端点（顶点 B）在内角内，则它是潜在的有效分割边。
原文
Cast two rays out along the edges connected to vertex A. The interior angle is the angle in the direction of the polygon. If the partition endpoint (vertex B) is within the interior angle, then it is a potential valid partition.
This second example is the same scenario with different vertices. Since the partition endpoint (vertex B) is outside the interior angle, it can't be a valid partition.
This algorithm is much easier to understand. It simply loops through all edges in the polygon and checks to see if the potential partition intersects with any of them. If it does, it isn't a valid partition.
Only if both algorithms pass is the partition considered valid.
Merging can only occur between the polygons created from a single contour. No attempt is made to merge polygons from adjacent contours.
Note that I have switched to the general form "polygon" rather than triangle. While initial merging will be between triangles, as the merge process proceeds non-triangle polygons may be merged with each other.
The process works as follows:
1. Find all polygons that can be merged.
2. From this list, select the two polygons with the longest shared edge and merge them.
3. Repeat until there are no further allowed merges.
Two polygons can be merged if all of the following conditions are met:
· The polygons share an edge.
· The resulting polygon will still be convex.
· The resulting polygon will not have more edges than allowed by the maxVertsPerPoly parameter.
Detecting shared edges and determining the merged edge count are both easy. Determining whether the merged polygon will be convex is a little more complex. The key to this check is the shared vertices. Both are checked for what they will look like after the merge. If both will form internal acute angles, then the merged polygon will still be convex. We determine this for each shared vertex as follows:
1. Create a directed reference line formed by the vertices just before and just after the shared vertex.
2. If the shared vertex is to the left of its reference line, then is forms an acute angle.
It is best to use visualizations. The first example demonstrates a valid merge.
如果把共享顶点标记为A，那么参考线将从顶点A-1到顶点A+1。顶点A在参考线的左侧吗?
原文
If the shared vertex is labeled A, then the reference line will be from vertex A-1 to vertex A+1. Is vertex A to the left of the reference line?
现在检查第二个共享顶点，它是否在其参考线的左侧？
原文
Now check the second shared vertex. Is it to the left of its reference line?
在下一个例子中，合并是无效的，因为如果合并发生，其中一个共享顶点将形成一个钝角内角。
原文
In this next example, the merge is invalid since one of the shared vertices will form an obtuse internal angle if the merge occurs.
If you are unfamiliar with the algorithm used to check the position of a point relative to a directed line, a good explanation is given at Soft Surfer. The core algorithm is implemented by the getSignedAreaX2() operation in the PolyMeshFieldBuilder.
The last step in this stage is to iterate through all the polygons in the entire mesh and generate connection information. While the algorithm is optimized, at its most basic level it simply steps through all the polygon edges and looks for other polygons that have an edge with the same vertices.
我们在哪
我们终于回到了向量空间，并得到一个凸多边形网格。
原文
We are finally back into vector space and have a mesh of convex polygons.
