从 2d 点创建 2d 三角形

Question

我必须从 2d 点列表中制作 2d 三角形，条件是：任何边的长度不能超过预定义的常数。

像这样：

你知道有什么算法可以做到这一点吗？或者有什么建议吗？

谢谢！

Answer 1

尝试 Delaunay 三角剖分，然后删除任何太长的边。

从上面的文章中，您可以看到CGAL 的 2D 三角测量页面的链接。

Answer 2

首先，生成所有可能的边（即连接比常数更近的一对顶点）。然后当其中两个相交时，删除其中一个。重复此步骤，直到没有交叉点。

这个解决方案相当原始，可能可以做得更快。

Answer 3

我喜欢斯维克的回答 -

实施时我会执行以下操作

1. 计算每对点之间的线
2. 按长度对列表进行排序
3. 删除所有长于阈值的行
4. 继续沿着列表向下（从最长到最短），如果它跨越另一行，则将其删除。

Answer 4

参加聚会有点晚了，但我遇到了类似的问题（具有边界约束的二维点集的三角测量）...

不幸的是，svick的算法结合pondulus的建议存在以下缺陷。考虑一个具有五个顶点的完整图，如图 所示。通过删除与端点之外的其他边相交的边（从最长到最短），可以得到图片的最后一个图形。显然，所得的边集不能产生三角测量。为了形式化三角剖分的概念，我们正在寻找“点之间不交叉边的最大集合”，如维基百科关于点集三角剖分的文章中所写。

这个问题有一个简单的解决方法：运行 svick 和 pondulus 算法后，我们得到一组边，它肯定只包含非交叉边，但不能是最大的（如示例中所示）。为了使这个集合成为三角剖分，我们可以再次迭代所有剩余的可能边并添加那些不与现有边相交的边。

虽然运行时间不是很好（对于 n 个点，我的实现行为类似于 O(n^3)；有关启发式，请参阅

），但我很欣赏在允许的边集上包含任何类型的约束的灵活性，例如最大长度，如 Mart 的问题或边界约束，如我的情况。