我想创建一个简单的 C++ 应用程序，给定 100 个随机点（带有凸包），它将对这些点的云进行三角测量。我已经搜索了这个主题，我可以看到 Delaunay 三角测量是一个选项，但我仍然无法理解如何实现它（例如在 c++ 中）。同样在下一个级别，我想将所有 Delaunay “非法”三角形绘制成不同的颜色，以更好地展示和理解 Delaunay 的算法。
谁能帮我理解如何对这些点进行三角测量？也许是一个小代码部分，或者通常是我需要实现的算法？
问问题
13824 次
3 回答
8
我强烈建议不要从头开始编写任何 Delaunay 三角剖分算法。如果我这样做是为了直观地理解算法的输出是什么样的，我会采用Johnathan Shewchuk 的三角形代码并对其进行修改以分配不同的颜色等。
但是，如果您有足够的动力从头开始实施，那么我的建议是在处理 3D 版本之前先实施 2D Delaunay 三角剖分。
于 2013-03-28T16:52:18.137 回答
4
如果你想同时了解三角剖分算法和 C++ 编码，那么 C++三角剖分组合项目可能看起来很诱人，但对于初学者来说肯定太难了。因此，我建议您在解决组合问题之前，先分别了解三角剖分的算法方面和C++ 的基础知识。
于 2013-03-28T18:19:50.887 回答
4
我想您需要先进行一般三角测量，然后修复所有不符合德劳内法律的问题？
一个非常糟糕的三角测量算法（带有一个糟糕的角度向量）是这样的：
(i) 获取点云的凸包 (ii) 将 CH 的一个随机点（使用第一个很方便）与 CH 的每个其他点连接（当然除了下一个和上一个，它与它已经形成边缘）。
（iiiA）对于平面上的每个其他点，如果该点位于三角形中，则通过将该点与其所在三角形的三个顶点连接起来，将其制成三个三角形。（iiiB）如果它位于边上（ 100 分有点不太可能，我想你可以跳过它），将它与它所在的四边形的另外两个顶点连接起来。
我想你可以从这个开始。云将被完全三角剖分，但可能超过一半的边缘将是 Delaunay 非法的。然后你可以继续修复（翻转）必要的边缘。
如果您发现实现它的问题，我可以提供一些示例代码来帮助您入门。现在请记住，算法的返回值可以方便地作为三角形的集合/向量；这样您就可以操纵它们并单独更改它们的颜色。
于 2013-03-29T13:42:55.910 回答