Menu
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.
489
The Delaunay triangulation is a triangulation which is equivalent to the nerve of the cells in a Voronoi diagram, i.e., that triangulation of the convex hull of the points in the diagram in which every circumcircle of a triangle is an empty circle (Okabe et al. 1992, p. 94).
Delaunay triangulation: Mainly centred on demonstrating in a practical way that it is always possible the tranformation between 2 triangulations of any points only using interchanges of edges.
Maximizing Angles and Edge Flipping: Another interesting property of Delaunay triangula- tions is that among all triangulations, the Delaunay triangulation maximizes the minimum angle. This property is important, because it implies that Delaunay triangulations tend to avoid skinny triangles.
ArcGIS supports the Delaunay triangulation method. The Delaunay triangulation ensures that no vertex lies within the interior of any of the circumcircles of the triangles in the network. If the Delaunay criterion is satisfied everywhere on the TIN, the minimum interior angle of all triangles is maximized.
If you want to construct the 2D Delaunay triangulation, use Triangle.Net. It is a direct C# port of Shewchuk's famous Triangle program.
164
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
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
