15

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

例如，考虑这个问题：

镶嵌

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

4

5 回答 5

3

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

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

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

2. 使用受约束的 Delaunay 进行三角剖分。

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

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

编辑查看其他实现的注释。

于 2013-03-15T16:05:51.110 回答
2

如果你想要一些更直接、更快的实现和更少的代码......我建议只做一些简单的多边形剪辑，就像过去的旧软件渲染算法一样（特别是因为你只处理三角形作为您的输入）。正如其他几个人简要提到的那样，它涉及在每个其他线段相交的点处拆分每个三角形。

三角形很容易，因为在给定平面上拆分三角形总是会产生 1 或 2 个新三角形（总共 2 或 3 个）。如果您的数据集相当大，您可以引入四叉树或其他形式的空间组织，以便在添加新三角形时更快地找到相交三角形。

在此处输入图像描述

当然，这将生成比建议的约束 Delaunay算法更多的多边形。但是其中许多算法在重叠形状方面表现不佳，并且需要您了解轮廓段，因此无论如何您都会做很多相同的工作。

如果需要更少的结果三角形，您总是可以在最后进行合并传递（在剪辑期间添加相邻信息以加快该部分的速度）。

无论如何，祝你好运！

于 2013-06-05T05:47:26.717 回答
1

您的示例是计算几何学所说的“排列”的一个特例。CGAL 库具有广泛而有效的安排处理例程。如果您查看文档的这一部分，您会看到您可以声明一个空排列，然后插入三角形以将 2d 平面划分为不相交的面。正如其他人所说，然后您需要对还不是三角形的面进行三角剖分。令人高兴的是，CGAL 还提供了执行此操作的例程。 这个受约束的 Delaunay 三角剖分示例是一个很好的起点。

CGAL 尝试使用可实现的最有效的算法。在这种情况下，对于具有 n 个边（在您的情况下是三角形数量的 3 倍）与 k 个相交的排列，您似乎可以实现 O((n + k) log n)。该算法使用一种称为“扫描线”的通用技术。一条垂直线从左到右扫过，沿途计算和处理“事件”。事件是边缘端点和交叉点。随着每个事件的处理，排列的一个单元格被更新。

对于 n 个顶点，Delaunay 算法通常是 O(n log n)。有几种常见的算法，很容易在 CGAL 参考资料中查找或找到。

即使您不能在您的工作中使用 CGAL（例如，出于许可原因），文档中也充满了底层算法的资源：安排和受约束的 Delaunay 算法。

但是请注意，由于浮点错误，排列和三角测量都很难正确实现。健壮的版本通常依赖于有理算术（在 CGAL 中可用）。

于 2013-03-19T00:35:57.717 回答
0

我可以想到两种方法。

一种更通用的方法是将您的输入视为一组行并将问题分成两部分：

  1. 多边形检测。取一组你的初始三角形制作的线，得到一组不重叠的多边形。本文提供了一种 O((N + M)^4) 方法，如果 N 是线段的数量，M 是交叉点的数量，不幸的是这似乎有点慢......
  2. 多边形三角剖分。从步骤 1 中取出每个多边形并对其进行三角剖分。这需要 O(n log* n)，实际上是 O(n)。

另一种方法是做一个自定义算法。解决两个三角形相交的问题，将其应用于前两个输入三角形，然后对于每个新三角形，将算法应用于所有当前三角形和新三角形。但是，即使对于两个三角形，这似乎也不是那么简单，因为有几种情况（可能并不详尽）：

  1. 三角形的任何点都不在任何其他三角形中。
    1. 没有交叉路口
    2. 犹太明星
    3. 两个垂直尖刺
  2. 一个三角形的一个点包含在另一个三角形中
  3. 每个三角形包含另一个点
  4. 一个三角形的两个点在另一个
  5. 一的三点在另一个中——一个被完全包含

等等......不，这似乎不是正确的方法。无论如何都要留在这里给后代。

于 2013-03-15T15:57:02.887 回答
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 等人的“计算几何：算法和应用”。

于 2013-03-15T16:11:54.940 回答