蛮力约束德劳内三角测量？

Question

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

我不能使用库。

我看了很多不同的算法。它们很多，很容易混淆。我想知道是否有一个天真的，因此希望更简单的算法，我可以用来生成右边的网格？蛮力方法很好（ps：我可以做Delaunay三角测量）。

Answer 1

感谢所有的答案。

我经历了为这个问题开发解决方案的过程，所以我想我会分享自己的经验，希望面对问题的人会发现洞察力很有用。

因此，根据我自己实施算法的经验，我得出结论：

1. 这个问题没有真正快捷的方法。认为只用50行代码就可以实现它是不合理的。事实上，我写的例程（C ++）大约有400到500行（很难用评论来表达）。如此合理紧凑但具有挑战性，我花了2至3天的时间来获得正确的逻辑（这可能很棘手）。
2. 我发现斯隆在"A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS"提出的算法非常适合手头的问题。关于Delaunay三角测量这对我来说是一个新主题的现实是，似乎有很多不同的算法方法，而且这项研究已经相当陈旧了。所以对于一个新来者来说，很难知道从哪里开始。 2.1。很难知道哪种算法是最新的，理解简单，实现快速简单。 2.2一般来说，一旦理解了原理，主要是以最有效的方式对逻辑进行编码（这似乎是大多数算法/论文在上面所争论的）。 2.3我发现斯隆的论文是可以理解的，非常好解释。如果你遵循逻辑和指令，那么任何人都可以真正实现受约束的Delaunay三角剖分。

总之：

1. 我推荐斯隆论文，因为它包括如何创建Delaunay三角剖分，然后在必要时进行受限三角测量的解释。
2. 要回答我自己的问题，这个问题并没有真正的蛮力。实现这种技术只需要实现完整的逻辑，大多数实现必须要求或多或少相同的工作量
3. 由于我的观点非常小，所以我没有考虑很多优化。所以我相信很多算法都比斯隆描述的算法更好;他们可能会提出优化的优化数据结构和算法，以最大限度地减少三角测量等点插入等步骤。

所以无论如何斯隆工作。一个小图像，以说明答案，使其更具吸引力;-)

EDIT

这是生产代码所以helas我无法分享...我可以引导我被解雇。但这个过程非常简单。您可以查找段（约束）与模型中所有边之间的交集。然后，对于每个相交的边，交换此边所属的2个三角形之间的对角线。如果新对角线仍与该段相交，则将新对角线添加回该段的相交边缘堆栈。如果新对角线不与段相交，则将其添加到新创建的边的堆栈中。继续处理相交边的堆栈，直到它为空。

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

这只是论文......

Point Set

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 - >顶点列表中的第一个顶点）

Answer 2

我尝试使用alpha形状，对于一些形状https://concavehull.codeplex.com/有良好的效果，但它远不及原始约束delaunay三角测量。

这是我的alpha形状算法：https://alphashape.codeplex.com。

Answer 3

一个简单的方法似乎是实现ear clipping算法。没有哈希网格或quad trees中的优化。对于耳朵剪辑，您只需检查每三个连续顶点a，b和c。如果b是凸的并且多边形的其他顶点不在三角形abc内，则可以剪切此三角形，将多边形的边界减少一个顶点，b。

此外，你必须存储邻里关系。因此，从每个三角形引用其最多三个邻居。

三角测量完成后，将其转换为受约束的Delaunay三角剖分（CDT）。这可以通过edge flipping完成。因此，你必须检查每个三角形的外接圆。如果相邻三角形的顶点不在三角形内，则符合CDT，否则翻转发生违规的三角形边缘。

由于@Betterdev在注释中编辑打击：可以通过添加桥来将输入多边形中的可能孔添加到初始边界。作为预处理，可以通过“双”边缘将孔的顶点连接到边界的顶点。这总是可行的，并使每个孔成为主多边形边界的一部分;适用于耳朵剪裁。然而，通过这些桥梁存储邻居对于翻转是至关重要的。

Answer 4

我以前在矢量图形包上工作，所以我不能告诉你我已经盯着那个确切的“e”图形了多少小时。我最终选择了earcut库来进行点数据的三角测量。与像libtess-2这样的库相比，它非常快速且简单得多。