蛮力约束的 Delaunay 三角剖分？
A Brute-Force Constrained Delaunay Triangulation?
我需要从一组点创建一个三角形网格。该集合的点数很少，因此不需要快速或优化（我最多处理 100 点）。网格需要受约束 "delaunay triangulation"。在下图中，我（在左侧）显示了我从中开始的一组点（蓝点和红点）。我也知道这些点之间的联系（黑色轮廓）。网格需要看起来像右边的示例（包括形成外部和内部三角形的灰色边缘）。
我不会使用库。
我研究了很多不同的算法。它们很多，很容易混淆。我想知道是否有一个天真的算法，因此希望我可以使用更简单的算法来生成右侧的网格？蛮力方法很好（ps：我可以进行 Delaunay 三角剖分）。
我尝试使用 alpha 形状对一些形状取得了不错的效果 https://concavehull.codeplex.com/ 但它与原始的约束 delaunay 三角剖分相去甚远。
这是我的 alpha-shape 算法：https://alphashape.codeplex.com.
一个简单的方法似乎是实施 ear clipping algorithm. Without optimisation as in hash grids or quad trees。对于耳朵剪裁，您只需检查每三个连续的顶点 a、b 和 c。如果 b 是凸的并且没有其他多边形顶点位于三角形 abc 内，那么您可以裁剪这个三角形，将多边形的边界减少一个顶点 b。
此外，您还必须存储邻里关系。因此，每个三角形最多引用其三个邻居。
完成三角剖分后，您将其转换为受约束的 Delaunay 三角剖分 (CDT)。这可以通过 edge flipping 来完成。因此，您必须检查外接圆的每个三角形。如果没有相邻三角形的顶点位于三角形内，则三角形符合 CDT 否则翻转发生违规的三角形边。
由于@Betterdev 在评论中的打击而编辑：可以通过添加桥将输入多边形中可能的孔添加到初始边界。作为预处理，可以通过 "double" 边将孔的顶点连接到边界的顶点。这始终是可能的，并且使每个孔成为主要多边形边界的一部分；并且适用于剪耳。然而，通过这些桥存储邻居对于翻转至关重要。
谢谢大家的回答。
我经历了为这个问题开发解决方案的过程，所以我想分享我自己的经验，希望遇到这个问题的人会发现有用的见解。
所以根据我自己实现算法的经验，我得出结论：
没有真正快速解决这个问题的方法。仅仅 50 行代码就可以实现的想法是不合理的。事实上，我编写的例程 (C++) 大约有 400 到 500 行（很难用注释来判断）。如此紧凑但具有挑战性，我花了 2 到 3 天的时间才弄清楚逻辑（这可能很棘手）。
我发现 Sloan 在 "A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" 中提出的算法非常适合手头的问题。当谈到 Delaunay 三角剖分这对我来说是一个新主题时，现实是似乎有很多不同的算法方法，而且这项研究已经很老了。所以对于一个新手来说，真的很难知道从哪里开始。
2.1。很难知道哪种算法是最新的，理解起来简单，实现起来又快又简单。
2.2 一般来说，一旦你理解了原理，主要就是以最有效的方式编写逻辑代码（而且这似乎是大多数 algorithms/papers 上面所反对的）。
2.3 我觉得斯隆的论文很好理解，解释的很好。如果您按照逻辑和说明进行操作，那么任何人都可以真正实现受约束的 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 -> 顶点列表中的第一个顶点）
我以前开发过一个矢量图形包，所以我无法告诉你我盯着那个确切的 "e" 图形看了多少小时。我最终选择了 earcut library for triangulation of point data. It's extremely fast and much simpler compared to libraries such as libtess-2.
我需要从一组点创建一个三角形网格。该集合的点数很少，因此不需要快速或优化（我最多处理 100 点）。网格需要受约束 "delaunay triangulation"。在下图中，我（在左侧）显示了我从中开始的一组点（蓝点和红点）。我也知道这些点之间的联系（黑色轮廓）。网格需要看起来像右边的示例（包括形成外部和内部三角形的灰色边缘）。
我不会使用库。
我研究了很多不同的算法。它们很多，很容易混淆。我想知道是否有一个天真的算法，因此希望我可以使用更简单的算法来生成右侧的网格？蛮力方法很好（ps：我可以进行 Delaunay 三角剖分）。
我尝试使用 alpha 形状对一些形状取得了不错的效果 https://concavehull.codeplex.com/ 但它与原始的约束 delaunay 三角剖分相去甚远。
这是我的 alpha-shape 算法：https://alphashape.codeplex.com.
一个简单的方法似乎是实施 ear clipping algorithm. Without optimisation as in hash grids or quad trees。对于耳朵剪裁，您只需检查每三个连续的顶点 a、b 和 c。如果 b 是凸的并且没有其他多边形顶点位于三角形 abc 内，那么您可以裁剪这个三角形，将多边形的边界减少一个顶点 b。
此外，您还必须存储邻里关系。因此，每个三角形最多引用其三个邻居。
完成三角剖分后，您将其转换为受约束的 Delaunay 三角剖分 (CDT)。这可以通过 edge flipping 来完成。因此，您必须检查外接圆的每个三角形。如果没有相邻三角形的顶点位于三角形内，则三角形符合 CDT 否则翻转发生违规的三角形边。
由于@Betterdev 在评论中的打击而编辑：可以通过添加桥将输入多边形中可能的孔添加到初始边界。作为预处理，可以通过 "double" 边将孔的顶点连接到边界的顶点。这始终是可能的，并且使每个孔成为主要多边形边界的一部分；并且适用于剪耳。然而，通过这些桥存储邻居对于翻转至关重要。
谢谢大家的回答。
我经历了为这个问题开发解决方案的过程，所以我想分享我自己的经验，希望遇到这个问题的人会发现有用的见解。
所以根据我自己实现算法的经验，我得出结论：
没有真正快速解决这个问题的方法。仅仅 50 行代码就可以实现的想法是不合理的。事实上，我编写的例程 (C++) 大约有 400 到 500 行（很难用注释来判断）。如此紧凑但具有挑战性，我花了 2 到 3 天的时间才弄清楚逻辑（这可能很棘手）。
我发现 Sloan 在 "A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" 中提出的算法非常适合手头的问题。当谈到 Delaunay 三角剖分这对我来说是一个新主题时，现实是似乎有很多不同的算法方法，而且这项研究已经很老了。所以对于一个新手来说，真的很难知道从哪里开始。
2.1。很难知道哪种算法是最新的，理解起来简单，实现起来又快又简单。
2.2 一般来说，一旦你理解了原理，主要就是以最有效的方式编写逻辑代码（而且这似乎是大多数 algorithms/papers 上面所反对的）。
2.3 我觉得斯隆的论文很好理解，解释的很好。如果您按照逻辑和说明进行操作，那么任何人都可以真正实现受约束的 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 -> 顶点列表中的第一个顶点）
我以前开发过一个矢量图形包，所以我无法告诉你我盯着那个确切的 "e" 图形看了多少小时。我最终选择了 earcut library for triangulation of point data. It's extremely fast and much simpler compared to libraries such as libtess-2.