如果我们有K组可能重叠的三角形，计算一种计算效率高的方法来计算一个新的、不重叠的三角形集合？
例如，考虑以下问题：
例如，考虑以下问题：
k路三角形集合交和三角剖分
15
- awdz9nld
3
我建议将此分为两个阶段：首先计算一组不重叠的多边形；然后根据需要对多边形进行三角剖分以获得三角形。后者问题已经有了很好的研究，并且网络上有很多资源。前者并不是一个常见的问题，但我认为也有很多相关资源。您需要决定结果是否应包括那些不属于任何原始三角形但被原始三角形所包围的形状（例如通过将蓝色三角形向右移动一点而形成的间隙）。 - Ted Hopp
2你需要找到并三角化联合多边形。这两个操作都可以使用扫描线算法完成。你可能能够将这些操作合并为单个过程。 - Vaughn Cato
@VaughnCato 我不确定union是否是满足上述需求的正确运算符（需要保留标识）。 - awdz9nld
5个回答
3
我建议采用两步法：
1. 找到所有三角形边的交点。正如评论所指出的那样，这是一个经过充分研究的问题，通常使用线扫描方法来解决。可以查看这篇文章，特别是Bentley-Ottmann算法。
2. 使用约束Delaunay三角剖分进行三角剖分。@Claudiu提出的多边形三角剖分可能无法解决您的问题，因为它不能保证包含所有原始边。因此，建议您查看约束Delaunay三角剖分。这些方法允许您指定必须包含在三角剖分中的边，即使它们不包含在非约束Delaunay或多边形三角剖分中也是如此。此外，还有一些实现允许您指定三角剖分的非凸边界，在边界之外不会生成任何三角形。这似乎在您的情况下也是一个要求。
实现约束Delaunay并不容易。然而，CMU研究人员提供了一个有点过时但非常好的C实现（包括命令行工具）。在这里可以查看这种算法的理论。此算法还支持边界的规定。请注意，链接的算法不仅可以做约束Delaunay（即生成高质量的网格），而且还可以配置为不添加新点，从而达到约束Delaunay的效果。
编辑：在评论中可以找到另一个实现。
1. 找到所有三角形边的交点。正如评论所指出的那样，这是一个经过充分研究的问题，通常使用线扫描方法来解决。可以查看这篇文章，特别是Bentley-Ottmann算法。
2. 使用约束Delaunay三角剖分进行三角剖分。@Claudiu提出的多边形三角剖分可能无法解决您的问题，因为它不能保证包含所有原始边。因此，建议您查看约束Delaunay三角剖分。这些方法允许您指定必须包含在三角剖分中的边，即使它们不包含在非约束Delaunay或多边形三角剖分中也是如此。此外，还有一些实现允许您指定三角剖分的非凸边界，在边界之外不会生成任何三角形。这似乎在您的情况下也是一个要求。
实现约束Delaunay并不容易。然而，CMU研究人员提供了一个有点过时但非常好的C实现（包括命令行工具）。在这里可以查看这种算法的理论。此算法还支持边界的规定。请注意，链接的算法不仅可以做约束Delaunay（即生成高质量的网格），而且还可以配置为不添加新点，从而达到约束Delaunay的效果。
编辑：在评论中可以找到另一个实现。
- DCS
1
3有一个带有多种语言实现的约束性Delaunay求解器可在BSD许可下获得，网址为https://code.google.com/p/poly2tri/。 - picomancer
2
如果你想要更简单、更快速实现且代码量显著减少的方法...我建议你只需像旧的软件渲染算法一样进行一些简单的多边形剪辑（特别是因为你只处理三角形作为输入）。正如其他人简短地提到的，这涉及将每个三角形在每个其他线段与其相交的点处分割。
三角形很容易处理，因为在给定平面上将三角形分割总是会产生1或2个新三角形（总共2或3个）。如果你的数据集很大，你可以引入四叉树或其他形式的空间组织，以便在添加新三角形时更快地找到相交的三角形。
当然，这将生成比建议的约束德劳内算法更多的多边形。但是许多这些算法无法处理重叠的形状，并且需要您知道轮廓线段，因此您仍然需要做同样的工作。
如果要求产生的三角形较少，您总可以在最后进行合并（在剪切期间添加邻居信息以加快该部分的速度）。
无论如何，祝你好运！
- user2454182
3
@jbaylina 哈！你说得对...抱歉，我忘记画其中一条线了。但你明白我的意思。 :) - user2454182
@jbaylina 很好，我仍然有桌面上的图片... 我编辑了我的回复！谢谢提醒。 - user2454182
对于那些需要在实时要求的应用程序中解决此问题的人来说，@Mattingly建议的方法已经被证明对于小输入更为可行。 - awdz9nld
1
你的例子是计算几何学家所谓的“安排”的一个特殊情况。CGAL Library拥有广泛而高效的安排处理例程。如果您查看文档的这一部分, 您可以声明一个空的安排，然后插入三角形来将二维平面划分为不相交的面。正如其他人所说，您需要对不是三角形的面进行三角剖分。令人高兴的是，CGAL也提供了执行此操作的例程。这个约束Delaunay三角剖分的例子是一个很好的起点。
CGAL尝试使用最有效的算法，以实现实际应用。在这种情况下，看起来您可以通过具有n条边（在您的情况下三角形数量的三倍）和k个交点的排列，实现O（（n + k）log n）。算法使用称为“扫描线”的通用技术。垂直线从左到右扫过，“事件”被计算并沿途处理。事件是边缘端点和交点。每处理一个事件，安排的单元就会更新。
对于n个顶点，Delaunay算法通常为O（n log n）。有几种常见的算法，可以轻松查找或在CGAL参考资料中找到。
即使您无法在工作中使用CGAL（例如出于许可证原因），文档也充满了底层算法的来源：排列和约束Delaunay算法。
请注意，由于浮点误差，安排和三角剖分都是出了名难以正确实现的。健壮版本通常依赖有理算术（在CGAL中提供）。
CGAL尝试使用最有效的算法，以实现实际应用。在这种情况下，看起来您可以通过具有n条边（在您的情况下三角形数量的三倍）和k个交点的排列，实现O（（n + k）log n）。算法使用称为“扫描线”的通用技术。垂直线从左到右扫过，“事件”被计算并沿途处理。事件是边缘端点和交点。每处理一个事件，安排的单元就会更新。
对于n个顶点，Delaunay算法通常为O（n log n）。有几种常见的算法，可以轻松查找或在CGAL参考资料中找到。
即使您无法在工作中使用CGAL（例如出于许可证原因），文档也充满了底层算法的来源：排列和约束Delaunay算法。
请注意，由于浮点误差，安排和三角剖分都是出了名难以正确实现的。健壮版本通常依赖有理算术（在CGAL中提供）。
- Gene
0
我可以想到两种方法。
一种更通用的方法是将您的输入视为一组行，并将问题分为两部分：
- 多边形检测。获取初始三角形所组成的线段集合，并得到一组不重叠的多边形。这篇论文提供了一种O((N + M)^4)的方法，其中N是线段数，M是交点数，但这似乎有点慢...
- 多边形三角剖分。对步骤1中的每个多边形进行三角剖分。这需要O(n log* n)，实际上是O(n)。
另一个方法是使用自定义算法。解决两个三角形相交的问题，将其应用于前两个输入三角形，然后对于每个新三角形，将算法应用于所有当前三角形和新三角形。虽然对于两个三角形来说，这似乎并不那么直接，因为有几种情况（可能不详尽）：
- 三角形中没有任何其他三角形的点。
- 没有交集
- 犹太星
- 两个垂直尖刺
- 一个三角形的一个顶点包含在其他三角形内
- 每个三角形都包含另一个的一个点
- 一个三角形的两个点在另一个三角形内
- 一个三角形的三个点在另一个三角形内 - 其中一个完全包含
等等……好像这不是正确的方法。无论如何，还是留在此处以备不时之需。
- Claudiu
0
稍微解释一下Ted Hopp的评论，这可以通过首先计算一个平面分割来实现，在该分割中，输出的每个有界面都与A'、B'、C'、AB、AC、BC、ABC或“无”之一相关联。然后第二阶段是在每个集合中三角化（可能是非凸）面。
第1步可以使用Bentley-Ottmann扫描线算法的变体在O((N+K)log N)时间内执行，其中当前集合作为算法状态的一部分进行维护。这可以从已经穿过的线段及其方向中确定。
完成后，每个集合的不相交多边形可以在O(N log N)时间内分成单调片段，然后可以在O(N)时间内对其进行三角剖分。
如果您还没有，请获取de Berg等人的《计算几何：算法和应用》一书。
第1步可以使用Bentley-Ottmann扫描线算法的变体在O((N+K)log N)时间内执行，其中当前集合作为算法状态的一部分进行维护。这可以从已经穿过的线段及其方向中确定。
完成后，每个集合的不相交多边形可以在O(N log N)时间内分成单调片段，然后可以在O(N)时间内对其进行三角剖分。
如果您还没有，请获取de Berg等人的《计算几何：算法和应用》一书。
- Andrew Durward
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接