CODEWITHSUNDEEP
c#.nettriangulationdelaunay
AlonH
AlonH

Reputation: 433

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.

Upvotes: 42

Views: 46147

Answers (5)

Pablo
Pablo

Reputation: 409

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

Upvotes: 16

Ashwin Nanjappa
Ashwin Nanjappa

Reputation: 78488

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

Upvotes: 18

wackmc
wackmc

Reputation: 19

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.

Upvotes: 1

blackbada_cpp
blackbada_cpp

Reputation: 432

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

Upvotes: 1

Mohit Vashistha
Mohit Vashistha

Reputation: 1904

Have you tried NetTopologySuite

Upvotes: 2

Related Questions