c++ - k路三角形集交点和三角剖分

Question

如果我们有 K 组可能重叠的三角形，那么计算一组新的、不重叠的三角形的高效计算方法是什么？

例如，考虑这个问题:

这里我们有 3 个三角形集合 A、B、C，它们有一些相互重叠，并希望得到不重叠的集合 A'、B'、C'、AB、AC、BC、ABC，例如AC 中的三角形将包含 A 和 C 之间完全重叠的曲面；并且 A' 将包含 A 的曲面，这些曲面不与任何其他集合重叠。

Answer 1

我(也)提出了一种两步法。

1.找出所有三角形边的交点。

正如评论中所指出的，这是一个经过充分研究的问题，通常使用线扫描方法来解决。这是 very nice overview ，尤其是 Bentley-Ottmann 算法。

<强>2。使用受约束的 Delaunay 进行三角剖分。

我认为@Claudiu 建议的多边形三角剖分无法解决您的问题，因为它不能保证包含所有原始边缘。所以，建议你看看Constrained Delaunay triangulations .这些允许您指定必须包含在三角剖分中的边，即使它们不会包含在不受约束的 Delaunay 或多边形三角剖分中。此外，还有一些实现允许您指定三角剖分的非凸边界，在该边界之外不会生成三角形。在您的情况下，这似乎也是一个要求。

实现受约束的 Delaunay 并非易事。然而，有一个有点过时但very nice C implementation可从 CMU 研究人员处获得(包括命令行工具)。见 here对于这个特定算法的理论。该算法还支持边界的规范。请注意，链接算法可以做的不仅仅是Constrained Delaunay(即质量网格生成)，但它可以配置为不添加新点，这相当于Constrained Delaunay。

编辑查看其他实现的评论。