一种暴力有约束的Delaunay三角剖分？

Question

一种暴力有约束的Delaunay三角剖分？

computational-geometrytriangulationdelaunay

6

我需要从一组点创建三角网格。这个集合只有很少的点，因此不需要快速或优化（最多处理100个点）。网格需要是受限制的“Delaunay三角剖分”。在下面的图像中，我展示了（左边）我从中开始的点集（蓝色和红色点）。我还知道这些点之间的连接（黑色轮廓）。网格需要看起来像右边的例子（包括形成外部和内部三角形的灰色边缘）。

我不能使用库。

我查看了许多不同的算法。它们很多，很容易混淆。我想知道是否有一个天真的算法，因此希望能更简单地生成右侧的网格？暴力方法可以（ps：我可以进行Delaunay三角剖分）。

- user18490

4个回答

1

我尝试使用alpha shapes算法对一些形状进行了测试，https://concavehull.codeplex.com/ 获得了不错的结果，但远不能与原始的约束Delaunay三角剖分相媲美。

这是我的alpha-shape算法: https://alphashape.codeplex.com。

- Micromega

非常感谢您的提示。我现在正在尝试Sloan算法（1992年），如果成功了，我会发布我的结果。如果不行，我会尝试/查看您的解决方案。 - user18490

@user18490：我读了一些Sloan的资料。在我看来，它不值得尝试，但你可以尝试Bowyer-Watson算法。你可以将其与Hilbert排序一起使用。但是Sloan不能解决CDT问题。 - Micromega

谢谢您的建议。我正在查看这篇论文：https://www.researchgate.net/profile/Scott_Sloan/publication/223642442_A_fast_algorithm_for_generating_constrained_Delaunay_triangulations/links/53d97ef60cf2e38c63362d6f.pdf。其中有一个CDT算法。我会研究一下您提到的其他技术。 - user18490

@Bettedev，看起来Bowyer-Watson算法给了我一个DT，但是我如何得到CDT呢？通过使用你提到的Hilbert排序吗？你能再具体一些吗？非常感谢。谢谢。 - user18490

@user18490：Ear-clipping算法不能生成dt。或者你可以试试我的算法 :)。 - Micromega

@user18490：我读了这篇论文，它使用四边形：http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ - Micromega

1

一种简单的方法似乎是实现剪耳朵算法，而不是像哈希网格或四叉树那样进行优化。对于剪耳朵算法，只需检查每三个连续的顶点a、b和c。如果b是凸的，并且多边形的没有其他顶点位于三角形abc内，则可以通过裁剪此三角形来将多边形的边界减少一个顶点b。

此外，您还需要存储邻域关系。因此，从每个三角形引用其最多三个邻居。

当三角剖分完成后，您将其转换为约束Delaunay三角剖分（CDT）。这可以通过边翻转完成。因此，您必须检查每个三角形的外接圆。如果相邻三角形的任何顶点都不在该三角形中，则符合CDT，否则翻转产生违规的三角形的边缘。

由于评论中 @Betterdev 的建议，可以通过添加桥将输入多边形中的可能漏洞添加到初始边界。作为预处理，可以通过“双重”边连接孔的顶点和边界的顶点。这始终是可行的，并使每个孔成为主多边形边界的一部分；并且与剪耳法很好地配合使用。但是，通过这些桥存储邻居对于翻转非常重要。

- gue

耳剪三角剖分是德劳内三角剖分吗？ - Micromega

1

@Betterdev 不，剪耳朵只是一种简单的三角剖分算法。这也是我将翻转算法描述为第二步的原因。边翻转将把三角剖分转换为CDT。 - gue

孔和交叉怎么办？ - Micromega

如果输入的多边形是简单的，就不应该有交叉。如果存在交叉约束，则可以使用扫描线或暴力计算交点并解决交叉问题。 - gue

斯隆算法怎么样？它能够三角化交叉和孔吗？ - Micromega

@Betterdev 是的，Sloan算法可以使用。孔洞应该不是问题，因为该算法适用于PSLG。我认为交叉点也可以通过一些预处理来解决。但我不知道实现Sloan算法会有多复杂。 - gue

0

我以前开发过矢量图形软件，所以我无法告诉你我注视那个完美的“e”图形花了多少小时。最终，我选择使用earcut库来三角剖分点数据。与libtess-2等库相比，它非常快速且更简单。

- Mapsy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user18490 · Accepted Answer

感谢您提供的所有答案。

我经历了解决这个问题的过程，所以想分享一下自己的经验，希望面临这个问题的人会发现这些见解有用。

因此，从我自己实现算法的经验中，得出以下结论：

没有快速解决这个问题的方法。认为只需要50行代码就可以实现是不合理的。实际上，我编写的程序（C++）大约有400到500行（很难确定是否包括注释）。它既紧凑又具有挑战性，并且花费了我2到3天的时间来正确理解逻辑（这可能很棘手）。
我发现Sloan在“生成受限Delaunay三角剖分的快速算法”中提出的算法非常适合手头的问题。当涉及到Delaunay三角剖分时，对于我来说，这是一个新课题，似乎有很多不同的算法方法，而且这项研究相当古老。因此，对于新手来说，很难知道从哪里开始。

2.1 很难知道哪个算法是最近的，理解起来简单且快速简单实现。

2.2 一般来说，一旦你理解了原则，大多数情况下只需要以最有效的方式编写逻辑（似乎这就是大多数算法/论文所争取的）。

2.3 我发现Sloan的论文易于理解，非常清楚地解释了。如果您遵循逻辑和说明，则任何人都可以实现受限Delaunay三角剖分。

因此，总之：

我推荐Sloan的论文，因为它包括如何创建Delaunay三角剖分，然后是必要的约束三角剖分的解释。
回答我的问题，实际上没有“蛮力”解决这个问题。实现这种技术只需要实现完整的逻辑，并且大多数实现可能需要更多或更少相同数量的工作。
有一个细微差别，即我并没有寻求太多优化，因为我的点集非常小。因此，我确信许多算法比Sloan描述的算法更好；它们可能提出了优化的数据结构和最小化步骤的算法，例如点插入三角剖分等。

总之，Sloan运作良好。一个小图像来说明答案并使其更有吸引力;-)

编辑

这是生产代码，所以很遗憾我不能分享它...这可能会导致我被解雇。不过，这个过程非常简单。您需要查找模型中一个线段（即您的约束）与所有边的交点。然后对于每个相交的边，您需要交换该边所属的两个三角形之间的对角线。如果新的对角线仍然与线段相交，则将新的对角线添加回此线段的相交边堆栈中。如果新的对角线不与线段相交，则将其添加到新创建的边的堆栈中。继续处理相交边的堆栈，直到为空为止。

完成上述步骤后，您需要处理新添加的边的列表。对于每个新添加的边，检查是否符合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开始（0->顶点列表中的第一个顶点）