强力约束德劳内三角剖分？
use*_*490 6 delaunay triangulation computational-geometry
我需要从一组点创建一个三角形网格。该集合的点数很少，因此不需要快速或优化（我最多处理 100 点）。网格需要是受约束的“delaunay 三角剖分”。在下图中，我（在左侧）显示了我开始的一组点（蓝色和红色点）。我也知道这些点之间的联系（黑色轮廓）。网格需要看起来像右侧的示例（包括形成外部和内部三角形的灰色边缘）。
我不能使用图书馆。
我研究了许多不同的算法。它们很多，很容易混淆。我想知道是否有一种简单且希望更简单的算法可以用来生成右侧的网格？蛮力方法很好（ps：我可以进行 Delaunay 三角剖分）。
感谢所有的答案。
我经历了开发这个问题的解决方案的过程，所以我想分享我自己的经验，希望面临问题的人们会发现这些见解有用。
因此，根据我自己实施算法的经验，我得出的结论是：
没有真正快速的方法来解决这个问题。认为仅仅 50 行代码就可以实现是不合理的。事实上，我编写的例程（C++）大约有 400 到 500 行（很难用注释来区分）。相当紧凑但具有挑战性，我花了 2 到 3 天的时间才弄清楚逻辑（这可能很棘手）。
我发现斯隆在“生成约束德劳奈三角的快速算法”中提出的算法非常适合当前的问题。事实上，德劳内三角测量对我来说是一个新课题，似乎有很多不同的算法方法，而且这项研究已经相当古老了。所以对于一个新人来说，真的很难知道从哪里开始。
2.1. 很难知道哪种算法是最新的、理解简单、实现起来又快又简单。
2.2 一般来说，一旦你理解了原理，主要就是以最有效的方式编码逻辑的问题（这似乎是上面大多数算法/论文所争论的问题）。
2.3 我发现斯隆的论文很容易理解，解释得很好。如果遵循逻辑和说明，那么任何人都可以真正实现约束 Delaunay 三角剖分。
所以结论是：
我推荐 Sloan 论文，因为它解释了如何创建 Delaunay 三角剖分，然后在必要时创建约束三角剖分。
要回答我自己的问题，这个问题并没有真正的暴力。实现此技术只需要实现完整的逻辑，并且大多数实现必须需要或多或少相同的工作量
就细微差别而言，我没有考虑太多优化，因为我的点集非常小。所以我确信很多算法都比斯隆描述的算法更好；他们可能会提出优化的数据结构和算法，以最大限度地减少三角测量中的点插入等步骤。
不管怎样，斯隆还是发挥了作用。一张小图片来说明答案并使其更具吸引力；-)
编辑
这是生产代码，所以我不能分享它......我可能会导致我被解雇。虽然过程非常简单。您寻找线段（您的约束）与模型中所有边之间的交集。然后，对于每个相交的边，交换该边所属的 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 -> 顶点列表中的第一个顶点）