k-way三角集交集和三角剖分

Question

如果我们有K组可能重叠的三角形,那么计算一组新的,不重叠的三角形的计算效率是多少？

例如,考虑这个问题:

这里我们有3个三角形集A,B,C,有一些相互重叠,并希望获得非重叠集A',B',C',AB,AC,BC,ABC,其中例如AC中的三角形将包含A和C之间独有重叠的表面; 和A'将包含A的表面,它们不与任何其他集合重叠.

Answer 1

我（也）提出了一个两步走的方法。

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

正如评论中指出的，这是一个经过充分研究的问题，通常采用线扫描方法来解决。这是一个非常好的概述，特别是 Bentley-Ottmann 算法。

2. 使用约束 Delaunay 进行三角测量。

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

实施约束 Delaunay 并非易事。然而， CMU 研究人员提供了一个有点过时但非常好的 C 实现（包括命令行工具）。看这里了解该特定算法的理论。该算法还支持边界指定。请注意，链接算法不仅可以执行 Constrained Delaunay（即质量网格生成），还可以将其配置为不添加新点，这相当于 Constrained Delaunay。

编辑请参阅另一个实现的评论。