42

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.

dtb
  • 213,145
  • 36
  • 401
  • 431
AlonH
  • 433
  • 1
  • 4
  • 7
  • it's strange it only can handle 20000 points; it only has O(n*log(n)) running time – Simone Sep 05 '11 at 14:59
  • 7
    Did you try the C# implementation at http://www.s-hull.org/ ? The algorithm it uses is supposed to be fast. – CodesInChaos Sep 05 '11 at 15:30
  • I've used the s-hull.org algo. Performance degrades significantly once you get to 100,000 or higher points, due to the phenomenal number of recursions going on in the code. Not sure how to beat it. I heard that there was another algo out there which reduces the recursiveness of the code, not sure what it was called (might have been De Wall or something). – code4life Sep 07 '11 at 18:41
  • 1
    Have you used qhull? Though that's not C#. – Joan Venge Jan 14 '12 at 01:30
  • 3
    What, for this particular problem, is "reasonable time", btw? Can you live with 60 second turnarounds? 1 second? 100ms? – Mike Feb 09 '12 at 16:06
  • 3
    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 Feb 10 '12 at 00:42
  • 1
    @Mike That's rather slow. Triangle should manage that many points in around 1s. – David Heffernan Mar 18 '12 at 17:42
  • I used Triangle and it worked well for me. http://www.cs.cmu.edu/~quake/triangle.html Good luck! Maxim – Maxim Eliseev Feb 09 '12 at 12:59
  • @Mike, 500k points & 30seconds, i think the performance is really nice, can you share it. – sendreams Jun 27 '15 at 06:21

5 Answers5

18

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

Ashwin Nanjappa
  • 76,204
  • 83
  • 211
  • 292
  • 6
    It appears that Triangle.Net is licensed under the MIT license, but apparently it's a straight port of Triangle to C#, and Triangle wasn't licensed under MIT. I doubt it's legality. – Eagle-Eye Jul 20 '14 at 06:45
  • I ended up using Triangle.NET myself. Using it for Unity 5, only had to fix two little things to get the .Net 4.5 to work with unity. – Mikael Högström Aug 07 '15 at 14:20
  • @MikaelHögström could you tell us what did you fix in triangle.net to make it work with unity? – seek Feb 21 '16 at 12:13
  • I don't remember exactly what but as I recall it wasn't too hard, took an hour or two I think. If you're stuck I could share my code with you! – Mikael Högström Feb 23 '16 at 10:26
  • This is the library that finally worked for me, particularly the Unity port found at github: https://github.com/parahunter/triangle-net-for-unity Created much more organic, non-grid-like results in my terrain gen endeavors. Thanks for posting this. It was rather easy to use and the DelaunayDemo in the Scenes folder of this Unity port is top notch. – Joseph Knight Apr 30 '16 at 12:37
  • 1
    As @MikaelHögström et al haven't doc'd their fixes, and the main site still has the bugs in current release, here's a link to the two fixes you need to do, takes approx 2 minutes: http://triangle.codeplex.com/discussions/651181 – Adam Jul 09 '16 at 20:10
  • For Unity 5, use [this](https://github.com/eppz/Triangle.NET/tree/Fix/Unity-fixes), it contains all necessary fixes. Tested with Unity 32 bit 5.5 and 5.6 on Windows 7. – Vignesh Jun 24 '17 at 23:49
  • 1
    @Eagle-Eye: Indeed. In particular, the original website says: "Please note that although Triangle is freely available, it is copyrighted by the author and may not be sold or included in commercial products without a license." – O. R. Mapper Jul 01 '18 at 21:27
16

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

Pablo
  • 399
  • 3
  • 6
  • Still does the trick. It sets up 500K points diagram in a matter of seconds. – OzrenTkalcecKrznaric Oct 22 '15 at 09:27
  • No downloads, no docs. Download page proudly says you can't downlod it, and you are instead required to interpret the proprietary project format, guess your way around til you find some source examples, and reverse-engineer the instructions. And it's GPLv3, which rules out a lot of uses. Not a great library! – Adam Jul 09 '16 at 20:09
  • 1
    If you take a look at the Github repo you will find that the source code is documented and it is licensed under MIT. – Pablo Sep 10 '16 at 18:41
2

Have you tried NetTopologySuite

Mohit Vashistha
  • 1,824
  • 3
  • 22
  • 49
  • This is a wrapper for JTS - which apparently does not support 3D - http://tsusiatsoftware.net/jts/jts-faq/jts-faq.html – JumpingJezza Mar 17 '16 at 03:57
1

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.

Styxxy
  • 7,462
  • 3
  • 40
  • 45
wackmc
  • 19
  • 1
1

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

blackbada_cpp
  • 422
  • 4
  • 11