Efficient Delaunay triangulation

问题:

I'm looking for a .NET implementation which builds Delaunay triangulation from set of points.

I have already tested couple of implementations but they all worked only for small amount of points (up to 20,000).

I need something that can handle 500,000 points in reasonable time.

回答1:

If you want to construct the 2D Delaunay triangulation, use Triangle.Net. It is a direct C# port of Shewchuk's famous Triangle program.

回答2:

I was looking for the same thing and I found a C# 4.0 library called MIConvexHull:

"A convex hull algorithm and library for 2D, 3D, and higher dimensions. The code can also be used to compute Delaunay triangulations and Voronoi meshes of the input data. The benchmarks indicate that the convex hull code and 4 and higher dimensional triangulation code is on par or better than the solution provided by the C++ library CGAL."

http://miconvexhull.codeplex.com/

Update Sep/2016:

This library has moved to Github and it seems that it is now released under the MIT license (some of the examples are GPL). You can find the latest version here:

https://github.com/DesignEngrLab/MIConvexHull

The documentation is actually in the source code and it is simple to use. Here is the relevant source file for Delaunay triangulation:

https://github.com/DesignEngrLab/MIConvexHull/blob/master/MIConvexHull/Triangulation.cs

If you want to see the original version from 2012. Take a look here:

http://miconvexhull.codeplex.com/SourceControl/changeset/view/e1b26677eb1a#MIConvexHull/Triangulation/Triangulation.cs

回答3:

Have you tried NetTopologySuite

回答4:

There is a C# implementation which could help you to generate Voronoy diagram as well as Delaunay triangulation: http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C

回答5:

There is a solution called G#.

It has Delaunay triangulations (also with breaklines). From the performance graph on their website you should be able to triangulate 500k points in about 30s.