带孔的多边形三角剖分

题

我正在寻找一个算法或库（更好）将多边形分解为三角形。我将在Direct3D应用程序中使用这些三角形。有哪些最佳选择？

这是我到目前为止所发现的：

我非常感谢那些在此领域有过经验的人的一些意见。

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

解决方案

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

其他提示

为您提供更多库选择：

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。

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

一般来说，我的建议是使用一些有用的东西，而不是开始编写自己的三角测量。

如果您已经阅读了关于耳朵剪切或扫描线算法的信息，那么很有可能会推出自己的算法，但事实上，计算几何算法难以编写，因为它们可以稳定工作，永不崩溃并始终返回有意义的结果。数值舍入误差最终会累积并杀死你。

我在C中为我合作的公司编写了一个三角测量算法。让核心算法工作需要两天时间。让它与各种退化的输入一起工作又花了两年时间（我没有全职工作，但相信我 - 我花了更多的时间在它上面而不是我应该拥有的）。

CGAL拥有您需要的工具：约束三角测量

您可以简单地提供多边形的边界（包括孔的边界）作为约束（最好是插入所有顶点，然后将约束指定为Vertex_handles对）。

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

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

您可以自己相对轻松地添加孔。基本上按照CGAL对输入点的凸包进行三角测量，然后删除任何三角形，其中心位于任何孔多边形内（或任何外部边界之外）。当处理大型数据集中的大量洞时，可以使用掩蔽技术来显着加快这一过程。

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

尝试libtess2

基于最初的SGI GLU tesselator（具有自由许可）。解决了许多小型mallocs的一些内存管理问题。

这是有限元分析中的常见问题。它被称为“自动网格生成”。 Google发现此网站，其中包含商业和开源的链接软件。他们通常会假设某种几何形状的CAD表示开始。

另一个选项（具有非常灵活的许可证）是从VTK移植算法：

此算法运行良好。可以直接使用它，但是需要链接到VTK，这可能比你想要的更多开销（尽管它还有许多其他不错的功能）。

它支持约束（孔/边界/等），以及对不一定在XY平面中的表面进行三角测量。它还支持我在其他地方没见过的一些功能（参见关于Alpha值的注释）。

我使用耳剪方法在C＃中实现了一个3D多边形 triangulator 。它易于使用，支持孔，数值稳健，并支持aribtrary（非自相交）凸/非凸多边形。

许可以下： CC-BY-SA 和归因