algorithm - 查找包含点云中所有点的最小三角形数

Question

输入

您有一个代表二维点云的点列表。

---

输出

您必须生成一个三角形列表(三角形应该尽可能少)，以便满足以下限制:

1. 云中的每个点都应该是三角形的顶点或者是在三角形内。

2. 三角形只能建立在点上原始点云。

3. 三角形不应与每个三角形相交其他。
4. 云中的一个点可以是多个三角形的顶点。
5. 如果三角形顶点位于另一个三角形的边上，我们假设这些三角形不相交。
6. 如果点位于三角形的边上，我们假设该点在三角形内部。

---

例如

---

调查

我发明了找到给定点集的凸包并将该凸包分成三角形的方法，但这不是正确的解决方案。

有什么办法解决吗？

Answer 1

这是我的看法。

1. 创建点云的 Delaunay 三角剖分。
2. 通过半边折叠进行网格简化。

对于第 1 步，三角剖分的边界将是凸包。如果您需要遵守非凸边界，也可以使用约束德劳内三角剖分 (CDT)。

对于第 2 步，半边折叠操作将保留现有顶点，因此不会添加新顶点。请注意，在您的情况下，折叠不会删除顶点，它们只会删除边缘。在应用边缘折叠之前，您应该检查您没有引入三角形反转(产生自相交)并且没有点位于三角形之外。折叠的顺序很重要，但您可以遵循通常的规则来衡量折叠的“成本”，即引入质量较差的三角形(即具有锐角的三角形)。因此，您应该尽可能选择产生最多等距三角形的折叠。

编辑:

折叠的顺序引导简化到不同的结果。除了最小化锐角之外，它可以由其他标准来指导。我认为可以通过选择产生填充最多的三角形与最空的三角形的折叠来最小化最空的三角形。所有标准仍然是启发式的。