找到包围点云中所有点的最小三角形数

Question

输入

您有一个表示2D点云的点列表.

---

产量

您必须生成三角形列表(应尽可能少的三角形) ,以满足以下限制:

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

2. 三角形只能在原始点云的点上构建.

3. 三角形不应相互交叉.
4. 云的一个点可以是几个三角形的顶点.
5. 如果三角形顶点位于另一个三角形的一侧,我们假设这些三角形不相交.
6. 如果点位于三角形的一侧,我们假设该点在三角形内.

---

例如

---

调查

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

任何猜测如何解决？

Answer 1

这是我的意见。

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

对于步骤 1，三角剖分的边界将是凸包。如果需要遵循非凸边界，还可以使用约束 Delaunay 三角剖分 (CDT)。

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

编辑：

折叠的顺序引导简化得到不同的结果。除了最小化锐角之外，还可以通过其他标准来指导它。我认为可以通过选择产生最填充的三角形与最空的三角形的折叠来最小化最空的三角形。尽管如此，所有标准都是主观主义的。