computational-geometry - 一个蛮力约束的 Delaunay 三角剖分？

Question

我需要从一组点创建一个三角形网格。该集合的点数很少，因此不需要快速或优化(我将最多处理 100 点)。网格需要是受约束的“delaunay 三角剖分”。在下图中，我(在左侧)显示了我从(蓝色和红色点)开始的一组点。我也知道这些点之间的联系(黑色轮廓)。网格需要看起来像右边的例子(包括形成外部和内部三角形的灰色边缘)。

我不能使用图书馆。

我研究了许多不同的算法。它们很多，很容易混淆。我想知道是否有一个简单的算法，因此我可以使用更简单的算法来生成右侧的网格？蛮力方法很好(ps:我可以做一个 Delaunay 三角剖分)。

Answer 1

感谢所有的答案。

我经历了开发这个问题的解决方案的过程，所以我想分享我自己的经验，希望遇到问题的人会发现这些见解有用。

因此，根据我自己实现算法的经验，我得出了以下结论:

没有真正快速的方法来解决这个问题。认为仅用 50 行代码就可以实现是不合理的。事实上，我写的例程(C++)大约有 400 到 500 行(很难用注释来判断)。如此合理紧凑但具有挑战性，我花了 2 到 3 天的时间才能使逻辑正确(这可能很棘手)。

我在 "A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" 中找到了 Sloan 提出的算法非常适合手头的问题。 Delaunay 三角剖分对我来说是一个新主题，现实情况是，似乎有很多不同的算法方法，而且这项研究已经很老了。所以对于一个新来者来说，真的很难知道从哪里开始。

2.1.很难知道哪种算法是最新的，理解起来简单，实现起来又快又简单。

2.2 通常，一旦您理解了原理，主要就是以最有效的方式对逻辑进行编码(这似乎是上面大多数算法/论文都在争论的问题)。

2.3 我发现 Sloan 的论文很好理解，解释得很好。如果您遵循逻辑和说明，那么任何人都可以真正实现受约束的 Delaunay 三角剖分。

所以总结一下:

我推荐 Sloan 论文，因为它解释了如何创建 Delaunay 三角剖分，然后在必要时进行约束三角剖分。

要回答我自己的问题，实际上并没有 蛮力到这个问题。实现此技术只需要实现完整的逻辑，大多数实现必须或多或少需要相同的工作量

由于细微差别，我并没有考虑太多优化，因为我的点集非常小。所以我确信很多算法都比 Sloan 描述的算法更好；他们可能会提出优化的数据结构和算法，以最大限度地减少三角测量中的点插入等步骤。

所以无论如何斯隆工作了。一张小图来说明答案并使其更具吸引力；-)



编辑

这是生产代码，所以我不能分享......我可能会导致我被解雇。不过这个过程非常简单。您在模型中寻找线段(您的约束)和所有边之间的交集。然后对于每条相交的边，交换该边所属的 2 个三角形之间的对角线。如果新的对角线仍然与线段相交，则将新的对角线重新添加到该线段的相交边的堆栈中。如果新的对角线不与线段相交，则将其添加到新创建的边的堆栈中。继续处理相交边的堆栈，直到它为空。

然后一旦完成，您需要处理新添加的边列表。对于其中的每一个，检查是否遵守 Delaunay 三角剖分标准。如果不交换此边所属的三角形的对角线。简单的 ...

这只是纸...

点集

26.9375 10.6875
32.75 9.96875
31.375 4.875
27.6562 2.0625
23.9375 -0.75
18.1562 -0.75
10.875 -0.75
6.60938 3.73438
2.34375 8.21875
2.34375 16.3125
2.34375 24.6875
6.65627 29.3125
10.9688 33.9375
17.8438 33.9375
24.5 33.9375
28.7188 29.4062
32.9375 24.875
32.9375 16.6562
32.9375 16.1562
32.9062 15.1562
8.15625 15.1562
8.46875 9.6875
11.25 6.78125
14.0312 3.875
18.1875 3.875
21.2812 3.875
23.4687 5.5
25.6562 7.125
8.46875 19.7812
27 19.7812
26.625 23.9688
24.875 26.0625
22.1875 29.3125
17.9062 29.3125
14.0312 29.3125
11.3906 26.7188
8.75 24.125

这些是 x/y/z 坐标 (z=0)

分割:

0 1
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
19 20
20 22
22 24
24 26
26 0
28 29
29 31
31 33
33 35
35 28

索引从 0 开始(0 -> 顶点列表中的第一个顶点)