高效的 Delaunay 三角测量

Question

我正在寻找一个 .NET 实现，它可以从一组点构建 Delaunay 三角剖分。

我已经测试了几个实现，但它们都只适用于少量点（最多 20,000）。

我需要可以在合理的时间内处理 500,000 点的东西。

Answer 1

如果要构建 2D Delaunay 三角剖分，请使用 Triangle.Net。它是 Shewchuk 著名的 Triangle 程序的直接 C# 移植。

Answer 2

我正在寻找同样的东西，我发现了一个名为 MIConvexHull 的 C# 4.0 库：

“适用于 2D、3D 及更高维度的凸包算法和库方面。该代码还可用于计算 Delaunay 输入数据的三角剖分和 Voronoi 网格。基准测试表示凸包代码和4维及更高维三角测量代码与以下提供的解决方案相当或更好 C++ 库 CGAL。”

2016 年 9 月更新：

这个库已经转移到了 Github，看起来它现在是在 MIT 许可证下发布的（一些示例是 GPL）。您可以在这里找到最新版本：

文档其实就在源码里，使用起来很简单。这是 Delaunay 三角剖分的相关源文件：

如果您想查看 2012 年的原始版本。请看这里：

Answer 3

2
投票

Answer 4

Answer 5

有一个解决方案称为G#。

它具有 Delaunay 三角剖分（也带有断裂线）。从他们网站上的性能图表来看，您应该能够在大约 30 秒内对 500k 点进行三角测量。