Earcut论文译文1

基于简化Earcut算法以确定性线性时间进行三角剖分

本文是翻译自《Deterministic Linear Time ConstrainedTriangulation using Simplified Earcut》。文中EarCut，我认为直接翻译成“耳切”有点怪，所以我保留了原文。

摘要

符合一组非相交输入片段的三角剖分算法通常以增量方式进行，首先插入点，然后插入线段。插入一个线段等同于：

（1）删除所有与它相交的三角形；

（2）使两个有着想要被删除线段作为共享边的多边形填充满因此而生成的空洞；

（3）分别对每个多边形进行三角剖分。

在这篇文章中，我们证明了凸顶点不是两个的多边形用Earcut方式生成三角形，不需要检查其他多边形点是否在每个Ear内部。事实上任何简单多边形都包含至少三个凸顶点，这就保证了存在一个有效的Ear用于切割，确保收敛。不仅如此，这就转化为一个最优的确定性线性时间三角剖分算法，而且这种算法也很容易实现。我们形式化地证明了我们的方法的正确性，并在实际应用中验证它，并与先前的研究进行比较。

1. 介绍

生成符合一组给定线段的三角化是许多科学计算工具的基础 [1], [2]。一个经典的构建约束三角化的方法是计算所有线段端点的一般三角化，然后合并线段。添加连接先前存在的三角剖分的两个顶点的线段需要执行两个操作：

图1：插入一个给定线段（图中线段s）在一个预先存在的三角剖分中，我们需要删除所有与它相交的三角形（图中黄色部分），揭示两个以线段s为基础的多边形区域。这些区域可能不是凸多边形，但赋予一个重要的属性：从其内部的任何一点都可以看到 s 的一部分。这可以通过观察这些完全由被线段s切割的三角形的部分组成的多边形来证明。因此每个子多边形的凸状保证了可见性，因此每个子多边形的凸性保证了可见性来。实际上，这避免了产生类似漩涡状的凹陷，而我们正是利用这一特性来加快其重新三角化的过程。

1. 检测并删除与该线段相交的所有三角形；

2. 填充生成的多边形孔，将两个子多边形填充为共享边的多边形，使得想要被删除的线段成为共享边（图1）。

在这个简短的论文中，我们聚焦于这个后者操作，为这个经典的计算几何问题提供一些新的见解，并最终提出了一个简单但计算效率极高的解决方案，而这个方案此前却一直被人们所忽视。

我们的主要观点是，在进行线段插入操作时所出现的所有多边形都属于一种受限的简单多边形类别，这类多边形不能存在严重的（类似卷曲的）凹陷。我们利用这个特性去设计一个简单的三角化算法，其以一种EarCut方式进行[3]，通过每次切除一个耳朵来形成三角形。我们能够证明，在我们所关注的这一类多边形中，除了两个顶点之外的所有凸顶点都能形成有效的“耳朵”，这些“耳朵”内部不包含任何其他顶点，因此可以直接用来构成三角形。我们也证明了任意多边形包含至少三个凸角，从而确保了算法的收敛性。将这些要素结合起来就得到了一个三角化算法，它是一个经典的EarCut算法的简化版本，我们省略了任何点在三角形内的测试。这种简化不仅使得算法更简单易于实现，而且它还使其以确定性线性时间运行，与已知的最佳三角化算法[4]相当，而该算法恰恰极难实现。

我们的线性化EarCut算法在该领域达到了领先水平，它要么采用了几个实现起来较为复杂的最优算法，要么采用了相对容易实现（尽管仍不如EarCut算法那样简单）但具有次优渐近复杂度的算法（第 2 节）。

在第三节，我们描述了经典的EarCut算法的原理，其复杂度为\(O(n^2)\)。在第四节，我们介绍了我们的简化版本，展示了它能在确定性线性时间内运行，并在第五节中证明了其正确性。在第六节，我们报告了我们对该方法进行的数值测试结果，还与该领域最近发表的方法（由Shewchuk和Brown在[5]中提出）进行了比较。

2. 预先工作

找到有效三角剖分多边形的方法是计算几何和计算机图形学领域数十年来一直面临的核心问题。在1978年之前没有有效的算法，并且唯一的方法是暴力法。暴力法——如EarCut[3]是流行的代表——非常容易实现，但同时它是低效的，并且只能实现\(O(n^2)\)复杂度。首次尝试对多边形进行高效三角剖分多边形的方法出现在 1978 年[6]，所提出的算法具有\(O(nlogn)\)时间复杂度。在一段时间内，人们认为三角化是一个与排序一样困难的问题，并且认为无法设计出更好的算法。Asano 等人[7]证明了对于有孔洞的多边形，这个限制是最优的，但不适用于简单多边形。Fournier和Montuno表明将一个简单多边形分解为梯形元素（梯形化）等价于三角化，并且每个梯形元素都可以在\(O(n)\)时间内进行三角化[8]。在那时最好的梯形化算法具有\(O(nlogn)\)复杂度，因此也是三角化的上限。在随后的几年，众多的研究者致力于梯形化技术，将其作为改进三角形化的一种手段，直到 1988 年Tarjan 和 Van Wyk [9]发现可以通过\(O(n\log{n}\log{n})\)的时间复杂度来实现梯形化（也就是三角形化）。在他们的论文中，Tarjan 和 Van Wyk提到了在未来不久有可能实现线性复杂度的可能性，并且在 1991 年Chazelle提出了提出了基于一种非常复杂的梯形化技术的确定性线性时间算法[4]。这些算法为了实现极高的效率而付出的代价是算法的复杂性。引用[5]，Chazelle’s的作品“被誉为理论上的突破，但被认为对于实际应用来说过于复杂”。查泽尔本人在其著名的文章结尾提出了一个问题，即是否存在更简单的算法，能够以最优时间三角化一个多边形。这个问题部分被解答在[10]，[11]。然而，这些方法仅通过随机方法获得了预期的线性时间复杂度，但在最坏情况下仍不是最优的。

通用算法有着丰富的文献资料，近年来并未出现重大改进。我们的工作并非旨在在这方面做出贡献，而是与一系列平行研究工作相关联，这些研究工作侧重于特定的应用（在我们这里就是约束三角剖分）。这些方法将适用范围限制在更狭窄的输入类别内，从而通过更简单且易于实现的算法来获得效率。考虑到这些三角化方法在科学计算中得到了广泛的应用，并且这些年来已经提出了许多针对它们的方法。Anglada [12]扩展了De Floriani和Puppo [13]的工作，提出了一种简单的\(O(nlogn)\)算法，用于在线段插入。根据[5]所述，这是实现这个类别的最简单的方法，但它在最坏情况下复杂度为\(O(n^2)\)。能够以确定性线性时间运行的方法也存在[14]，[15]。该领域的最新进展是[5]，它结合了简洁性和效率，通过随机化方法实现了预期的线性时间复杂度。

还有一种方法能在确定性的线性时间内运行[16]，但是它基于梯形化，并且很难实现。我们证明了像earcut这样的暴力算法经过简单的修改后，可以获得最佳确定的线性时间复杂度，并且我们的修改甚至简化了原算法的实现。至此，不仅我们的方法具有最佳复杂度，而且它比任何已知的技术更容易实现，包括暴力算法。

3. 背景：经典EarCut

在本节中，我们介绍EarCut算法的基本原理，并统一相关符号的使用。给定由顶点循环列表定义的简单多边形 P其顶点列表为\({v_1,v_2,...,v_n}\)，任意一个顶点v ∈ P如果它的内部角小于π则是凸顶点，否则是凹顶点。对于任意两个非连续的点\(v_i,v_j ∈ P\)，如果它完全包含在多边形中，那么线段\(v_iv_j\)是P的一条对角线。给定一个凸顶点，如果它的两个相邻顶点形成一条对角线，则从P中分离一个角（或者说“耳朵”）。众所周知的，任何简单多边形都包含至少两个“耳朵”[17]；通过逐步分离它们来构造三角化的算法其被称为Earcut算法，其可以说是已知最简单的三角化算法[3]。

虽然它很简单，但是Earcut是相当耗费性能。原生实现的复杂度是\(O(n^3)\)，其中n是多边形顶点的数量。如果分别为凸顶点和凹顶点预计算单独的列表，可以将复杂度降低到\(O(n^2)\)[3]，但仍然远远超出简单多边形的最佳三角化算法承诺的线性时间复杂度（第2节）。然而，当真正编码时，因为它的实现非常简单，所以Earcut总是一个诱人的解决方案。

什么使得Earcut算法效率低下，是对角线测试。对于任何在凸顶点中心的候选“耳朵”，算法必须验证其左侧和右侧的邻居是否形成对角线。这实际上是要确保由这三个顶点所构成的三角形不包含任何其他多边形的顶点，这可以通过逐一测试来在线性时间内完成。由于三角化多边形的n个顶点包含n-2个三角形，并且测试一个耳朵是线性的，所以总体成本最多为二次方。

4. 线性Earcut

在这一章节，我们介绍我们简化版本的Earcut算法，并讨论其复杂度。证明算法的正确性和收敛性将在第5节给出。

---

算法1：线性Earcut

---

  输入：一个简单多边形\(P={v_1,v_2,...,v_n}\)，且顶点经过排序使得\((v_1,v_n)\)是约束段的端点   输出：一个\(P\)的三角化

1 // 用双链表表示多边形，更新花费的复杂度是\(O(1)\)

2 \(P={n,1,2,...,n−1}\) // 预先（prev）

3 $N={2,3,...,n,1} $// 下一个（next）

4 // 预先计算内部的“耳朵”,花费是\(O(n)\)

5 \(E = \emptyset\) // 译者注释：一开始是E是空集

6 for i = 2,3,...,n−1 do

7  if \(v_i\) 是凸顶点 then

8    添加\(v_i\) 到 \(E\)

9  end

10 end

11 // 处理内部的耳朵，花费为\(O(n)\)

12 while \(|E|>0\) do

13  v = 从\(E\)中取出一个“耳朵” 0 14  创建三角形\(P(v),v,N(v)\)

15  // 更新邻居点位，花费是\(O(1)\)

16  \(N(P(v))=N(v)\)

17  \(P(N(v))=P(v)\)

18  // 检查前一个或者后一个是否为新的“耳朵”，花费是\(O(1)\)

19  if \(P(v) \notin E \cup \{v_1,v_n\}\)且\(P(v)\)是凸顶点，则

20   添加\(P(v)\)到\(E\)

21  end

22  if \(N(v) \notin E \cup \{v_1,v_n\}\)且\(N(v)\)是凸顶点，则

23   添加\(N(v)\)到\(E\)

24  end

25 end

---

在算法1中，我们展示了我们的线性Earcut算法的伪代码实现。我们的代码基于文献[3]中高效的实现，并进一步简化以充分利用我们多边形的特殊性质。给定一个描述简单多边形的有序顶点链\({v_1,v_2,...,v_n}\)描述一个简单多边形，并且假设\(v_1,v_n\)是我们想要插入到网格中的约束线段，算法如下进行：我们首先初始化多边形的双向链表表示，这相当于两个长度为 n 的数组（译者注：原文是vector，翻译成向量也没什么错，但是从伪代码中看，这个应该是数组的意思。如同c++中的vector），分别用于编码每个点在链中的前一个和下一个顶点。这个方式非常高效的，因为删除多边形中的节点只需要更新其邻居的前后信息，从而从链中排除它（伪代码行15-17）。然后，我们处理所有顶点，除了约束线段的极值，并检查它们是否是凸顶点的或凹顶点的。所有凸性检查都使用精确的方向判断[18]，因此算法是数值稳定的。与标准的Earcut不同，凸顶点直接被认为是有效的“耳朵”，因此它们不需要对角线测试（在第 5.2 节中有详细证明）。

最终，我们剪切了所有的“耳朵”：对于每一个耳朵的中心凸顶点v，我们首先创建用在链表中它钱一个和后一个顶点创建三角形（在伪代码行13-14），并且从多边形中移除v。最后，如果“耳朵”的极值点不是凸顶点，我们检查他们现在是否变成了凸形，如果是则我们将他们添加到“耳朵”列表中。当所有的“耳朵”都被切掉后算法终止，从而得到输入多边形的三角化。

4.1 复杂度

这很容易证明上述的算法运行在一个确定的线性时间中，这意味着其复杂度在最坏情况下与多边形的顶点数量呈线性关系。这内部“耳朵”的预先计算（行4-10）总共计算了 n-2 个的内角（约束线段的极值不考虑），因此复杂度为\(O(n)\)。while循环（行11-25）的执行次数与多边形的耳朵数量相同。我们从Euler定理可知，具有 n 个顶点的简单多边形可以恰好用 n - 2 个元素进行三角化，这意味着代码中的循环将被确切地执行 n-2 次。在循环中，我们三角形的生成复杂度为\(O(1)\)，双向链表的更新也是\(O(1)\)，检查新的“耳朵”，只需要检查我们刚刚切掉的“耳朵”的两侧，因此复杂度是\(O(1)\)。所以，整个复杂度是\(Θ(n)\)。

5. 正确性证明

我们证明我们的线性Earcut保证收敛到一个有效的三角化。证明的大致思路如下：我们首先描述我们方法保证适用的多边形的类型（章节 5.1）。然后，我们证明所有内部的“耳朵”（即所有凸顶点，但不包括约束线段的极值）都可以在\(O(1)\)时间内安全地切割，从而回避对角线测试（章节 5.2）。反之，两侧的“耳朵”（即约束线段的极值）可能无效，且在切除前总是需要做对角线测试（章节 5.3）。最后，我们证明了对于任何在我们研究的多边形类别中，总存在一个内部的“耳朵”，从而保证在最坏情况下收敛（章节 5.4）。

5.1 多边形属性

图2，基于约束线段（虚线）的两个多边形的所有内部凸顶点定义一个凸子多边形（绿色），该子多边形确保了这些顶点是有效的“耳”结构。右下角：约束线段的极值总是凸的，但它们可能定义出无效的“耳”结构，这些结构无法用于三角化。

图3，沿着非直接连接约束线段 s 端点的链中的任何凸顶点 v 保证不包含其他多边形顶点在它"耳朵"内。这可以通过观察到 v 也是一个子凸多边形（绿色阴影区域）的顶点。凸性保证了绿色多边形的所有非后续顶点都能形成有效的"耳朵"。因此，v 也是原始多边形的一个有效"耳朵"。

图4，上面：所有三角形的外轮廓与约束线段相交的部分可能会覆盖到底层网格中未被 s 相交的边，从而产生悬空边（左图）、空洞（中图）或两者兼有的情况（右图）。采用基于拓扑的方法从底层网格中提取多边形，能够在处理这些异常情况时做到准确处理，通过沿着链条（底部）复制具有两个以上相邻顶点的顶点。因此，从拓扑角度来看，这些多边形始终是简单的，但在这些异常情况下，它们会包含几何上重合的顶点或边。者是二者皆有（右边的）。用拓扑学的方法可以得到推断，底层网格可以正确处理这些病态的情况。沿着链条（底部）两个

我们关注的是在受约束三角形化简过程中所产生的多边形的拼接问题，当要在先前已存在的三角形网格\(M(V,T)\)中插入一条新边段 s 时，由 s 与所有三角形的交集所构成的多边形具有该边段作为对角线。沿着 s 将该多边形均分后，会得到两个子多边形，必须对这两个子多边形进行三角形化处理，以便将边段 s 转化为网格 M 的一条边（图1）。

正如文献[13]中所指出的，在这种情况下产生的多边形是简单的，即它们不会自相交，也不会包含内部孔洞。注意到没有与线段相交的原生网格边可能会留置被困在多边形内部，从而生成悬空边，空洞或两者兼备的情况。然而，通过在底层网格上按顺序提取多边形边界的方法，如[5]，它保证了不会有简单的点位被复制，且总是得到一个简单的拓扑多边形，如果发生非正常情况，该多边形也可能包含几何上重合的顶点（图4）。

我们在本文中得出的关键观察结果是这些多边形属于一个受限的形状类别，这使得它们比一般的简单多边形更容易进行三角剖分。实际上，给定一个线段 s 和基于该线段的两个多边形，我们观察到即使是凹面，但在多边形内部的任何一点都能看到 s 的一部分，只要多边形以线段为基础。这一观察结果已在文献[13]中提出，并源于这样一个事实，我们希望进行三角剖分的多边形是由从新线段截取的部分三角形组成的，因此每个子元素的凸性保证了可见性（图1）。更正式地说，这类多边形被称为弱可见的[19]。这一特性避免了出现严重的（类似卷曲的）凹角，使我们能够避开修改后的Earcut算法中的对角测试。

5.2 内部“耳朵”（Internal ears）

给定一个多边形 P ，我们证明沿着间接连接约束线段 s 的端点的链中的任何凸顶点 v 都形成一个有效的“耳朵”。换句话说，分别用\(v_l,v_r\)表示 v 的左侧和右侧的两个顶点，我们可以证明\(\widehat{v_l v v_r}\)的内部不包含多边形 P 的任何其他顶点。我们证明我们的理论通过表明\(v_l,v,v_r\)也是一个凸子多边形Ω（\(Ω ⊆ P\)）的顶点。凸状保证了Ω中任何一对不相邻的顶点都能形成有效的对角线，包括\(v_l\)和\(v_r\)的连接。

为便于说明，让我们聚焦在 v 的左边。根据对称性，在其右侧也能生成相同的结构。如果\(v_l\)不是 s 的一个端点，则边\(\widehat{v_lv}\)属于在底层网络中的一个三角形\(t_l\)，并且这个三角形它的第三个顶点在 s 的另一侧。这种情况总是会发生的，因为如果这些点位在 s 相同的一侧，则\(t_l\)则不会与该线段相交，也不会是多边形P的一部分。链接三角形顶点的边（与\(v_l\)的\(\widehat{v_l v}\)相反），和线段 s 相交在点\(\overset˜v_l\)。同样的，那里也存在一个孪生顶点\(\overset˜v_r\)，它是通过在右侧重复相同的构造而得到的。

点\({v,v_l,\overset˜v_l,\overset˜v_r,v_r}\)形成一个五边形\(Ω ⊂ P\)(图3)。它很容易证明出\(Ω\)是严格的凸边形，实际上：

• 依据我们的初始的假定，v是\(P\)的一个凸顶点，因此在 \(Ω\) 中它的角度严格小于π；

• \(v_l\)是三角形\(t_l\)的内部顶点，因此它的角度严格小于π；

• \(\overset˜v_l\)被定义为三角形边和线段 s 相交的点。这个交点将2π分成了4个角，全都严格小于π；

• 由于对称性，对于 \(v_l\) 和 \(\overset˜v_l\) 所确定的角度范围，对于 \(v_r\) 和 \(\overset˜v_r\) 也同样适用。

因为 \(Ω\) 是凸边形，因此任何连续的三个顶点构成的三元组都能形成一个有效的“耳朵”，包括以v做中心的“耳朵”

注意到，在 \(v_l\) 或者 \(v_r\) 是 s 的端点的情况下， \(Ω\) 是四边形。如果两个都是 s 的端点，则 \(Ω\) 是一个三角形且和 P 一致。在这两种情况下，\(Ω\)的内部角仍然严格在π范围内，因此它的凸性和所有它的“耳朵”的有效性是可以被保证的。在图 2 中，我们展示了对于图 1 所示示例，所有保护内部“耳”的凸子多边形。

5.3 侧"耳"（Lateral ears）

约束线段 s 的极值总是形成与 P 形成凸顶点。这一点可以通过观察得出，即如果它们的角度大于或等于 π，那么包含它们的三角形一开始就不会与 s 产生交集。然而，在章节5.2中描述的构造方法不适用于侧"耳"，因为它们的一边和 s 重合，而且存在一个包含该边且完全位于 P 内的凸子多边形这一条件并不一定成立。在图2的右下角，我们展示了一个失败的例子，其中由侧耳形成的三角形甚至都不在 P 内。请注意，即使侧耳形成有效的三角形的情况仍可能发生，但如果没有进行对角测试，就不能安全地对其进行裁剪，因此处理它们的计算成本是\(O(n)\)。基于这个原因，我们永远不会考虑侧"耳"在我们的三角剖分算法中。

5.4 内“耳”的存在（Existence of internal ears）

为了证明时间复杂度收敛在确定的线性时间，我们证明对于在章节 5.1 中描述的任何多边形，总存在一个内部的“耳”可以被裁剪在\(O(1)\)时间内（章节 5.2 ）。首先，我们观察到任何简单多边形都至少有三个凸顶点。这可以通过观察到简单多边形所有内部角和总是 \((n-2)π\) 来证明。假设只有两个凸顶点，角度 \(α,β > 0\)。根据凹顶点的定义，剩余的 n-2 个顶点的角度之和必须大于或等于 \((n-2)π\) 。将两个凸顶点的角度之和加到一起，我们得到\((n-2)π+α+β\)，这已经大于多边形所有内部角度之和（n-2）π，从而导致矛盾。但是，如果一个多边形包含至少三个凸顶点，并且恰好有两个侧“耳”，那么第三个凸顶点必须是内部的“耳”。

6. 实验验证

我们已经实现了我们的线性Earcut算法并且将它与最新的相关算法进行了比较，该算法基于Shewchuk和Brown在[5]中提出的算法。与我们的算法一样，他们的方法是专门为章节 5.1 中所描述的多边形类别三角化而设计的，但它是随机的，因此具有仅期望线性时间复杂度。他们的算法产生了输入多边形的约束Delaunay三角剖分（Constrained Delaunay Triangulation，CDT），使用Chew的算法[20]来在期望线性时间内细分在违反Delaunay条件的子多边形中。我们观察到直接比较是不公平的，因为我们的约束三角剖分不一定具有Delaunay属性。因此，我们重新实现了Shewchuk和Brown的算法，而省略了Chew的模块和内切圆测试，因此算法仅产生一般的三角剖分，而不需要获得Delaunay属性。我们使用这个版本来进行我们的实验比较。

两个算法都用C++实现，使用配备有Intel Core i5 2.9GHz且16GB内存的MacBook Pro作为测试硬件。考虑到我们方法的简单性，将在算法1中的伪代码变为实际代码只需要我们不到一个小时（参考实现可以在CinoLib [21]中找到，链接如下 https://github.com/mlivesu/cinolib/blob/master/include/cinolib/segment_insertion_linear_earcut.h）。[5]也被认为相对易于编程，并且作者报告说花费五个小时来从他们的伪代码开始实现算法。在我们的个人经验中，我们需要两天的时间来完全理解算法并制作计算机程序。实现Chew的子模块（我们省略了）可能还需要一些额外的时间。

关于实验，我们遵循了[5]中相同的验证方案，该方案测量运行时间随输入大小的增长，在两个顶点数量不断增加的参数多边形上进行测量。尽管这两个多边形并不能完全涵盖实际应用中可能出现的所有情况，但它们足够复杂，能够揭示关键配置和瓶颈[5]。为了完整性，我们还进行了第三次“真实环境”实验，使用文献[22]中提出的工作流（译者注：原文的pipeline，正如渲染管线一样，我觉得这里要翻译为工作流，后文也是如此）内的两个三角化算法来计算网格排列，并在 Thingi10K 数据集[23]中包含的 4K 交叉网格上运行软件。

图5，参数化测试多边形用以与[5]进行比较。下边缘对应于约束段，上边缘可以容纳不同数量的顶点（在左模型中的所有顶点均共线，在右模型中则沿垂直轴随机偏移）。

图6，我们方法（蓝色）与文献[5]中提出的随机算法（红色）的时间对比情况，是基于图 5 中的两个多边形得出的。水平轴反应了多边形的数量，垂直轴是运行时间（以秒为单位）。对于每一个多边形大小，我们考虑1000次尝试的平均运行时间。两个算法都呈现线性增长的时间，但我们的方法大约快两个数量级。

参数多边形。我们分别对图 5 中所示的参数形状以及具有 10 到 1000 个顶点的多边形这两种情况下的算法进行了测试。对于每一个多边形，我们对1000次尝试的平均运行时间进行平均，以避免因外部因素而产生的偏差。结果如图6所示。两种算法在运行时间上都随着输入规模的增加而呈线性增长，但我们的方法起伏更少且明显地更快。对于这个不同的其中一个可能原因是[5]在其迭代期间可能会生成与先前生成的三角形冲突的三角形，这些三角形必须要被移除。这不仅在算法中增加没必要的延迟，而且还需要一些网格数据结构来处理拓扑变化，并检查每个新生成的三角形的邻域，以检查是否存在冲突。相比之下，Earcut仅生成将在输出细分中出现的合法三角形，并且在执行过程中不需要任何支持的网格数据结构。请注意，如果要构建CDT，我那么我们的方法至少还需要具备以下能力：能够找到给定边的相对顶点以进行内切圆测试，以及一个边翻转操作符以确保满足德劳内性质。即使在这种情况下，也不会因删除非法三角形而产生额外成本。

在真实情况下的网格排列。计算网格排列的过程就是对输入的三角形集合进行细化处理，以便将交点纳入连通性之中。经典工作流通过分别对每个三角形进行细化，首先添加交点，然后纳入当两个三角形相交时产生的约束段。后一步操作可以通过使用约束三角剖分算法来实现。我们运行了[22]中提出的工作流进行两次运行，一次使用我们针对段插入的线性化耳切方法，一次使用[5]中提出的方法。在线段插入步骤上的时间，和随之引起的多边形三角化，在Thingi10K数据集[23]中包含的4408个交叉网格上，我们的方法总共花费了18分钟，使用[5]中提出的方法花费了23分钟。在大多数情况下，两个方法之间的差异都非常小（也就是小于\(1e^{-5}\)秒），但总体上，我们的方法在4408中的3969个模型比[5]快，显示了即使在实际情况下，我们的方法也比最新的成果更快。

7. 总结和未来的工作

我们提出了一种新的算法，能够在确定性的线性时间内对一类特定的平面多边形进行三角化，这类多边形出现在约束三角化的场景中。这类多边形的分形通常会在科学计算中出现，因此所提出的这种方法具有实际应用价值。此前文献中已有几种确定性的线性时间算法，但它们都基于复杂的梯形化方案，并且难以实现。因此，在实践中反而使用了最多以二次、对数或非确定性线性时间运行的更简单（虽然不是最优）的方法。

我们的方法将最优性保证与易于实现性相结合，因为他是基于[3]中提出的耳切算法的进一步简化，这是可论证的最简单的（但效率很低）三角化算法之一来实现。我们证明了通过省略对角线测试，耳切算法可以实现最佳性，并且如果输入多边形属于我们所关注的类别，则可以保证正确结果。我们还提供了对我们的发现的严格证明，以及实际证据表明，该算法在实际应用中更快。由于这些关键特征，我们期望将来对生成约束三角化的代码采用我们的工具。

7.1 未来工作

我们的方法不考虑网格质量，因此三角形的形状可以非常糟糕。这里有两个主要的方式去提高三角化质量：一个是使用类似于[5]中提出的方法来构建Delaunay三角剖分，这是适合我们的工作流；或者使用我们的线性化Earcut的随机或者有优先度的版本，它修改了处理顺序的耳朵，并且通常能生成比基于连续处理的标准版本[24]更好的三角剖分。注意，Delaunay和优先级耳切都会改变算法的复杂度，而随机耳切则保持确定性的线性特性。

除了质量之外，这项工作还为未来的研究开辟了两条有趣的方向。一方面，如果在 3D 中也能证明类似性质，这可能会为受约束的体积网格化提供最优的时间算法。不过，这种扩展并非显而易见的。对于 2D 情况，证明包围凸顶点的子多边形的凸性的一个关键要素是：给定一条边，包含该边的三角形总是其第三个顶点位于受约束段的对面。而在 3D 中，约束既可以是平面多边形也可以是线段。关于处于一条线段对面的概念并不明确。此外，可能存在与约束相交的四面体，其两个顶点位于其中一侧，而另外两个顶点位于另一侧。目前我们证明的逻辑方案中，这种配置如何处理尚不清楚。尽管如此，在 3D 中，并非所有凹多面体都可以在不使用额外（Steiner）点[25]的情况下进行三角化，甚至确定是否有可能进行三角化也是 NP 级的困难[26]。不可分解的多面体可能会在工作流的任何步骤中出现，导致死锁。第二项有趣的研究方向是并行化。在文献[27]中，引入了标准耳切算法的并行版本。将同样的并行化方案应用于我们的线性化Earcut算法似乎是可行的，并且可能会为约束三角剖分带来次线性段插入操作。

引用

[1] J. R. Shewchuk, “Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator,” in Workshop on Applied Computational Geometry. Springer, 1996, pp. 203–222.

[2] J.-D. Boissonnat, O. Devillers, M. Teillaud, and M. Yvinec, “Trian gulations in CGAL,” in Proceedings of the sixteenth annual symposium on Computational geometry, 2000, pp. 11–18.

[3] D. Eberly, “Triangulation by ear clipping,” Geometric Tools, pp.2002–2005, 2008.

[4] B. Chazelle, “Triangulating a simple polygon in linear time,” Discrete & Computational Geometry, vol. 6, no. 3, pp. 485–524, 1991.

[5] J. R. Shewchuk and B. C. Brown, “Fast segment insertion and incremental construction of constrained Delaunay triangulations,” Computational Geometry, vol. 48, no. 8, pp. 554–574, 2015.

[6] M. R. Garey, D. S. Johnson, F. P. Preparata, and R. E. Tarjan, “Triangulating a simple polygon,” Information Processing Letters, vol. 7, no. 4, pp. 175–179, 1978.

[7] T. Asano, T. Asano, and R. Y. Pinter, “Polygon triangulation: Efficiency and minimality,” Journal of Algorithms, vol. 7, no. 2, pp. 221–231, 1986.

[8] A. Fournier and D. Y. Montuno, “Triangulating simple polygons and equivalent problems,” ACM Trans. Graph., vol. 3, no. 2, pp. 153–174, 1984.

[9] R. E. Tarjan and C. J. Van Wyk, “An O(nloglogn)-time algorithm for triangulating a simple polygon,” SIAM Journal on Computing, vol. 17, no. 1, pp. 143–178, 1988.

[10] N. M. Amato, M. T. Goodrich, and E. A. Ramos, “A randomized algorithm for triangulating a simple polygon in linear time,” Discrete & Computational Geometry, vol. 26, no. 2, pp. 245–265, 2001.

[11] ——, “Linear-time triangulation of a simple polygon made easier via randomization,” in Proceedings of the sixteenth annual symposium on Computational geometry, 2000, pp. 201–212.

[12] M. V. Anglada, “An improved incremental algorithm for con structing restricted Delaunay triangulations,” Computers & Graphics, vol. 21, no. 2, pp. 215–223, 1997.

[13] L. De Floriani and E. Puppo, “An on-line algorithm for constrained Delaunay triangulation,” CVGIP: Graphical Models and Image Pro cessing, vol. 54, no. 4, pp. 290–300, 1992.

[14] T. C. Kao andD.M.Mount,“Incremental construction and dynamic maintenance of constrained Delaunay triangulations,” in Proc. 4th Canad. Conf. Comput. Geom, 1992, pp. 170–175.

[15] D.-T. Lee and A. K. Lin, “Generalized Delaunay triangulation for planar graphs,” Discrete & Computational Geometry, vol. 1, no. 3, pp. 201–217, 1986.

[16] F. Chin and C. A. Wang, “Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time,” SIAM Journal on Computing, vol. 28, no. 2, pp. 471 486, 1998.

[17] G. H. Meisters, “Polygons have ears,” The American Mathematical Monthly, vol. 82, no. 6, pp. 648–651, 1975.

[18] J. R. Shewchuk, “Adaptive precision floating-point arithmetic and fast robust geometric predicates,” Discrete & Computational Geometry, vol. 18, no. 3, pp. 305–363, 1997.

[19] D. Avis and G. T. Toussaint, “An optimal algorithm for deter mining the visibility of a polygon from an edge,” IEEE Computer Architecture Letters, vol. 30, no. 12, pp. 910–914, 1981.

[20] L. P. Chew, Building Voronoi diagrams for convex polygons in linear expected time. Dartmouth College, Department of Mathematics and Computer Science, 1990.

[21] M. Livesu, “cinolib: a generic programming header only C++ library for processing polygonal and polyhedral meshes,” Transactions on Computational Science XXXIV, 2019, https://github.com/mlivesu/cinolib/

[22] G. Cherchi, M. Livesu, R. Scateni, and M. Attene, “Fast and Robust Mesh Arrangements using Floating-point Arithmetic,” ACM Trans. Graph., vol. 39, no. 6, pp. 250:1–250:16, 2020.

[23] Q. Zhou and A. Jacobson, “Thingi10k: A dataset of 10,000 3d printing models,” arXiv preprint arXiv:1605.04797, 2016.

[24] M. Held, “FIST: Fast industrial-strength triangulation of polygons,” Algorithmica, vol. 30, no. 4, pp. 563–596, 2001.

[25] E. Sch¨onhardt, “ ¨ Uber die Zerlegung von Dreieckspolyedern in Tetraeder,” Mathematische Annalen, vol. 98, pp. 309–312, 1928.

[26] J. Ruppert and R. Seidel, “On the Difficulty of Triangulating Three Dimensional Nonconvex Polyhedra,” Discrete & Computational Geometry, vol. 7, no. 3, pp. 227–253, 1992.

[27] G. Eder, M. Held, and P. Palfrader, “Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons,” Computational Geometry, vol. 73, pp. 15–23, 2018

原文地址

https://arxiv.org/pdf/2009.04294

闲言碎语

        又是一篇困难的翻译，全部翻译完我才发现这不就是在吹牛皮吗？实际上对应的相关知识点都没有提及，全部翻译完我也不知道Earcut算法原理到底是什么。文中掺杂着各种长难句和对应的术语，实在是太难理解了。因此文中很多都是借用有道翻译 + 各种AI协调去做翻译的。我做这个唯一的好处就只能是磨练我的英语翻译能力了。但是我现在好像也不怎么用得到英语翻译就是了。算了，算了，后面有机会我在好好研究下Earcut吧。