论文标题
确定性线性时间限制了三角剖分，使用简化耳塞
Deterministic Linear Time Constrained Triangulation using Simplified Earcut
论文作者
论文摘要
符合一组非交流输入段的三角剖分算法通常以增量方式进行，首先插入点，然后再插入段。插入段的等同：（1）删除与其相交的所有三角形； （2）用两个具有通缉段作为共享边缘的多边形填充所产生的孔； （3）分别对每个多边形分别进行三角测量。在本文中，我们证明了这些多边形，以至于它们的所有凸顶点，但两个都可以用耳塞形成三角形，而无需检查其他多边形点是否位于每个耳朵内。任何简单的多边形都包含至少三个凸顶点的事实确保存在有效的耳朵，从而确保收敛。这不仅可以转化为最佳确定性线性时间三角算法，而且这种算法也可以实现。我们正式证明了方法的正确性，还可以在实际应用中验证它，并将其与先前的艺术进行比较。
Triangulation algorithms that conform to a set of non-intersecting input segments typically proceed in an incremental fashion, by inserting points first, and then segments. Inserting a segment amounts to: (1) deleting all the triangles it intersects; (2) filling the so generated hole with two polygons that have the wanted segment as shared edge; (3) triangulate each polygon separately. In this paper we prove that these polygons are such that all their convex vertices but two can be used to form triangles in an earcut fashion, without the need to check whether other polygon points are located within each ear. The fact that any simple polygon contains at least three convex vertices guarantees the existence of a valid ear to cut, ensuring convergence. Not only this translates to an optimal deterministic linear time triangulation algorithm, but such algorithm is also trivial to implement. We formally prove the correctness of our approach, also validating it in practical applications and comparing it with prior art.
