Efficient Delaunay triangulation

41
votes

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.

5
c#.nettriangulationdelaunay
Did you try the C# implementation at s-hull.org ? The algorithm it uses is supposed to be fast. – CodesInChaos
Have you used qhull? Though that's not C#. – Joan Venge
What, for this particular problem, is "reasonable time", btw? Can you live with 60 second turnarounds? 1 second? 100ms? – Mike
I just wrote a C# triangulator which takes ~30seconds on 500K input data points, non-parallelized. Don't know if that's useful or not, I can post it. – Mike
@Mike That's rather slow. Triangle should manage that many points in around 1s. – David Heffernan

5 Answers

19
votes

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

16
votes

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

1
votes

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

1
votes

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.