高效的Delaunay三角剖分

我正在寻找一个.NET实现，从一组点构建Delaunay三角剖分。高效的Delaunay三角剖分

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

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

2011-09-05 AlonH

这很奇怪，它只能处理20000点;它只有O（n * log（n））运行时间 – Simone

您是否在http://www.s-hull.org/上试过C＃实现？它使用的算法应该是快速的。 – CodesInChaos

我已经使用了s-hull.org算法。由于代码中出现的递归数量惊人，一旦达到100,000或更高点，性能就会显着降低。不知道如何击败它。我听说有另一个算法，它减少了代码的递归性，不确定它被称为什么（可能是De Wall或其他）。 – code4life

2012-01-28 11:48:22 Mohit

这是JTS的封装 - 显然不支持3D - http://tsusiatsoftware.net/jts/jts-faq/jts-faq.html – JumpingJezza

2012-03-01 19:16:55 BlackBada

我一直在寻找同样的事情，我发现了一个C＃4.0库称为MIConvexHull：

“用于二维，三维和更高维度的凸包算法和库，该代码还可用于计算输入数据的Delaunay三角剖分和Voronoi网格，基准表明凸包代码和4和更高的尺寸三角测量代码与C++库CGAL提供的解决方案相比甚至更好。“

更新月/ 2016：

这个库已经转移到Github上，似乎现在是在MIT许可下（一些的例子是GPL）发布。你可以在这里找到最新版本：

的文件实际上是在源代码，它是简单易用。下面是Delaunay三角相关的源文件：

如果你想看到从2012年的原始版本看看这里：

2012-08-17 17:47:05 Pablo

仍然有诀窍。它在几秒钟内设置了500K点图。 – OzrenTkalcecKrznaric

没有下载，没有文档。下载页面自豪地说，你不能下载它，而你需要解释专有的项目格式，猜你的方式，直到你找到一些源代码示例，并反向工程的说明。它是GPLv3，它排除了很多用途。不是一个好的图书馆！ – Adam

如果你看看Github的回购，你会发现源代码被记录下来，并且它在MIT的授权下。 – Pablo

有一个叫G#解决方案。

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

2012-11-04 22:58:07 wackmc

不好的框架，而不是免费的 –

如果要构建2D Delaunay三角测量，请使用Triangle.Net。它是Shewchuk着名的Triangle程序的直接C＃端口。

2013-07-04 03:22:32

你真棒:)。我在寻找完全一样的东西：D – Flamy

看起来Triangle.Net是根据MIT许可证获得许可的，但显然它是一个三角形到C＃的直接端口，Triangle未经MIT许可。我怀疑这是合法的。 –

我最终自己使用了Triangle.NET。将它用于Unity 5，只需修复两个小问题即可使.Net 4.5与Unity一起工作。 –

回答