带孔的多边形三角网

问题描述：

我正在寻找算法或库（更好）将多边形分解为三角形。我将在Direct3D应用程序中使用这些三角形。什么是最佳可用选项？带孔的多边形三角网

这是我迄今发现：

我真的很感谢有此方面经验的人的一些意见。

编辑：这是一个2D多边形。

你需要2D（三角形）还是3D（四面体）？ – 2009-01-02 08:52:41

这是一个二维多边形 – 2009-01-02 09:30:18

答

乔纳森Shewchuk的Triangle library是惊人的;我过去曾用它来自动化三角测量。你可以要求它试图避免小/窄的三角形等，所以你想出了“好”的三角形而不是任何三角形。

答

你可以相对容易地自己添加洞。基本上按照CGAL对输入点的凸包进行三角化，然后删除任何三角形，该三角形的中心位于任何空洞多边形内（或任何外部边界之外）。在处理大型数据集中的大量漏洞时，可能会使用掩膜技术显着加快此过程。

编辑：这项技术的一个常见扩展是在船体上除去最长边缘或最小内角超过给定值的弱三角形。这将形成一个更好的凹形船体。

这种方法不起作用：您需要使用约束三角测量，否则，您可能会遇到三角形，这些三角形部分位于孔内，部分位于孔外。 – Camille 2009-01-02 12:29:08

@camille - 带洞的三角形多边形总是受到限制。根据定义，多边形的边和孔是有限制的。如果三角形边缘穿过一个孔，则孔将被部分覆盖。如果它跨过多边形边，则TIN不会是该多边形的三角形。 – 2009-01-02 13:03:09

答

CGAL有你需要的工具： Constrained Triangulations

您只需提供您的多边形（incuding孔的边界）为约束条件（最好的是，你插入所有顶点，然后指定的边界约束作为Vertex_handles对）。

然后，您可以通过任何遍历算法标记三角形的三角形：从入射到无限顶点的三角形开始，并将其标记为外部，并且每次跨越约束时，切换到相反的标记（在if你之前将三角形标记为局外人，如果之前将三角形标记为内幕人士以外）。

对于简单情况来说，它是一个很好的解决方案。如果您有重叠的孔和孔内的孔，它会翻倒。我更喜欢有明确的内部和外部界限。 – 2009-01-02 13:29:11

如果你有重叠的洞，你应该保留你已经输入的洞列表（而不只是一个内部/外部标签）。除此之外，它完全一样。 – Camille 2009-01-03 21:34:38

答

为了给你更多的图书馆选择：

Polyboolean。我从来没有试过这个，但它看起来很有希望：http://www.complex-a5.ru/polyboolean/index.html

General Polygon Clipper。这个在实践中效果很好，并且可以进行三角测量以及裁剪和打洞：http://www.cs.man.ac.uk/~toby/alan/software/

我个人的建议：使用GLU（OpenGL Utility Library）中的tesselation。该代码是坚如磐石的，比GPC更快并且生成更少的三角形。您不需要初始化的OpenGL-Handle或类似的东西来使用lib。

如果您不喜欢将OpenGL系统库包含在DirectX应用程序中的想法，那么还有一个解决方案：只需下载SGI OpenGL参考实现代码并从中提取三角函数即可。它只是使用OpenGL-Typedef的名字和一个充满枚举的手。而已。您可以提取代码并在一两个小时内创建一个独立的lib。

在一般情况下，我的建议是使用一个有效的工具，并且不会开始编写自己的三角测量。

如果您已经阅读了耳廓修剪或扫描线算法，那么您很有可能会推出自己的产品，但事实是计算几何算法难以置信，难以用稳定的工作方式编写，永远不会崩溃并始终返回有意义的结果。数值舍入误差会累积并最终杀死你。

我用C语言为我的公司编写了一个三角测量算法。获得核心算法工作需要两天时间。让它与各种退化的投入一起工作又过了两年（我没有全职工作，但相信我 - 我花了更多的时间在它上面）。

答

这是有限元分析中的一个常见问题。它被称为“自动网格生成”。谷歌发现this site与商业和开源软件的链接。他们通常假设几何的CAD表示要开始。

答

另一种选择（具有非常灵活的许可证）是从端口VTK算法：

该算法的工作相当好。直接使用它是可能的，但需要链接到VTK，它可能比你想要的更多的开销（尽管它还有许多其他很好的功能）。

它支持约束（孔/边界/等），以及对不一定在XY平面中的表面进行三角测量。它还支持我在别处没有看到的一些功能（请参阅有关Alpha值的注释）。

答

尝试libtess2

在原有基础上SGI GLU tesselator（与自由的许可）。解决了许多小型malloc周围的一些内存管理问题。

答

我发现poly2tri库正是我所需要的三角测量。它产生比我尝试过的其他库（包括libtess）更清洁的网格，并且它也支持漏洞。它已被转换为一堆语言。许可证是New BSD，所以你可以在任何项目中使用它。

答

我已经实现使用耳削波方法的3D多边形triangulator在C＃。它很容易使用，支持孔，数值稳健，并支持多边形（非自相交）凸/非凸多边形。