我想创建一个简单的C++应用程序，给定100个随机点（用它们的凸包），它将三角化这些点的云。我已经搜索了这个主题，我可以看到，Delaunay三角测量是一个选项，但我仍然不明白如何实现这个（例如在c + +中）。同样在下一级，我想绘制所有Delaunay“非法”三角形的颜色，以更好地展示和理解Delaunay的算法。点云三角剖分算法
任何人都可以帮助我理解如何对这些点进行三角测量？也许是一个小的代码部分或通常我需要实现的算法？
我想你首先需要一个通用的三角剖分，然后修复所有不符合德洛奈法律的东西？
一个极坏的三角剖分算法（具有坏角度矢量）是这样的：
（ⅰ）获取点云的凸壳 （ⅱ）连接CH的随机点（它的方便使用第一个）与CH的每个其他点（当然除了下一个和前一个，它已经形成一个边缘）。 （iiiA）对于平面中的每个其他点，如果该点位于一个三角形中，则通过将该点与其所在的三角形的三个顶点相连来制作三个三角形。 （iiiB）如果它位于一个边缘（有点不可能100分，我想你可以跳过它），将它与其所在的四边形的其他两个顶点连接。
我想你可以从这开始。云将被完全三角化，但可能超过一半的边缘将是Delaunay非法的。然后你可以继续修理（翻转）必要的边缘。
如果您发现实施它的问题，我可以提供一些示例代码来帮助您入门。现在要记住，算法的返回值对于三角形的集合/矢量来说很方便;这样你可以操纵它们并单独改变它们的颜色。
我会强烈建议不是从头编码任何Delaunay Triangulation算法。如果我这样做是为了直观地理解算法的输出结果，我会采取Johnathan Shewchuk's Triangle code并对其进行修改以指定不同的颜色等。
但是，如果您有足够的动机来从头开始实施，那么我的建议就是先解决2D版Delaunay Triangulation，然后再解决3D版。
感谢您的回答和时间！首先，我想简单地对这100个点进行三角测量。有没有一个简单而全面的方法来做到这一点？我见过像耳朵剪辑等算法，但我仍然无法理解它们（或在C++中实现它们）。 –
如果您只希望对这100个点进行三角测量，您是否可以使用其他人编写的软件？如果是这样，那么看看这个：http://www.codeproject.com/Articles/492435/Delaunay-Triangulation-For-Fast-Mesh-Generation（我还发现一个StackOverflow后讨论Delaunay和Voronoi：http：// stackoverflow .com/a/9240121/1384030） –
我不想使用现成的解决方案，因为我需要通过编码来了解它。如果你有更多的建议，我会很高兴！谢谢你到目前为止！ –
如果您想了解三角的两种算法及其在C++编码，然后将结合项目编码C++三角看似诱人的，但可以肯定的是太难初学者。因此，我建议你先学习约三角的算法方面和的的C++seperately基础知识你处理合并问题之前。
这似乎不是编码问题，而是三角测量。 – Walter
但我对三角测量和编码感兴趣 –