Efficient Delaunay triangulation

Question

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.

Answer 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.

Answer 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

Answer 3

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

Answer 4

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.

Answer 5

Have you tried NetTopologySuite