Livesu Marco, Cherchi Gianmarco, Scateni Riccardo, Attene Marco
IEEE Trans Vis Comput Graph. 2022 Dec;28(12):5172-5177. doi: 10.1109/TVCG.2021.3070046. Epub 2022 Oct 26.
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 article 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.
符合一组不相交输入线段的三角剖分算法通常以增量方式进行，先插入点，然后插入线段。插入一条线段相当于：(1) 删除它相交的所有三角形；(2) 用两个以所需线段为共享边的多边形填充如此生成的空洞；(3) 分别对每个多边形进行三角剖分。在本文中，我们证明这些多边形具有这样的性质，即除了两个顶点外，它们所有的凸顶点都可以以耳切方式用于形成三角形，而无需检查其他多边形点是否位于每个耳内。任何简单多边形至少包含三个凸顶点这一事实保证了存在一个有效的可切割耳，从而确保收敛。这不仅转化为一种最优的确定性线性时间三角剖分算法，而且这种算法实现起来也很简单。我们正式证明了我们方法的正确性，还在实际应用中对其进行了验证，并与现有技术进行了比较。
