我强烈建议不要从头开始编写任何Delaunay三角测量算法.如果我这样做是为了直观地了解算法的输出结果,我会采用Johnathan Shewchuk的三角形代码并对其进行修改以指定不同的颜色等.
但是,如果你有足够的动力从头开始实现这一点,那么我的建议是在你解决3D版本之前首先实现2D Delaunay三角测量.
我想您首先需要进行一般三角测量，然后修复所有不符合 Delaunay 法律的内容？
一个非常糟糕的三角测量算法（具有错误的角度向量）是这样的：
(i) 获取点云的凸包 (ii) 将 CH 的随机点（使用第一个点很方便）与 CH 的每个其他点（当然下一个和上一个点除外，用它们来连接）已经形成边缘）。
(iiiA) 对于平面上的每个其他点，如果该点位于三角形中，则通过将该点与其所在三角形的三个顶点连接起来，将其制成三个三角形。 (iiiB) 如果它位于一条边上 ( 100点有点不太可能，我想你可以跳过它），将它与它所在的四边形的另外两个顶点连接起来。
我想你可以从这个开始。云将被完全三角化，但可能超过一半的边缘将是德劳内非法的。然后你可以继续修复（翻转）必要的边缘。
如果您发现实现它时遇到问题，我可以提供一些示例代码来帮助您入门。现在请记住，算法的返回值如果是三角形的集合/向量会很方便；这样你就可以操纵它们并单独改变它们的颜色。