DelaunayJL is an incremental 2D Delaunay triangulation algorithm implemented in Julia, it is robust and ~20% faster than CGAL, the C++ de-facto industry standard. And it's MIT Licensed! all links to code are below
The figure below shows how much time it takes to run a benchmark on my computer, an Intel Core i7-4800MQ CPU @ 2.7Ghz, 16GB RAM, Win8 64bit. The benchmark consists of inserting a number of points uniformly distributed. The benchmark is run 5 times for each number of points once for CGAL and once for Julia. The numbers of points used are 10K, 100K, 1M, and 10M. CGAL v4.4 was compiled with VS2013 64bit release mode, Julia is of version 0.3.0 Commit 7681878 (2014-08-20 20:43 UTC) x86_64-w64-mingw32 the delaunay code is here (see other gists of mine for complementing files... I'll compile this all into a library when I have the time)
this is the code for the Julia benchmark:
and this is the code for the CGAL benchmark:
Note that the CGAL benchmark measures also the time needed to allocate memory for the Delaunay construction. In Julia it is pre-allocated. I think pre allocation is the idiomatic thing to do when you have a gc, and I couldn't separate the allocation in the C++ code, so this is the way it is. Fair or not, at least I don't hide this :)
Fisrt, take a look in the examples demostrating some random and regular distributions:
Then, take a look in the code. It contains several tests both for the predicates and the Delaunay construction. A couple of tests build a tesselation from a random distribution of 10000 points and then checks explicitly that every point lays outside any circle built by any other triangle in the tesselation. This is repeated also for a regular point distribution. Also some very small tessellations are built and checked "manually" for correctness. If you find a bug however, let me know :)
Note that for Delaunay construction the orientation is always known so I commented out the initial orientation calculation from the predicates code. So if you run the predicates tests the ones testing for orientation will currently fail. Uncomment the code and they will pass. I need to find a solution so this code can be used both for the Delaunay construction and as general predicates.
Both CGAL and Julia implementations use an incremental approach. Both use a scale free spatial sorting, so diffferent distributions (as long as they are general position) should not make a difference in the timings. Therefore, for e.g., I didn't test for clustering. In fact the spatial sorting is exactly the same: a complete random shuffle, followed by multi-scale Hilbert-median sorting. All the thresholds and ratios used for multi-scale sorting and Hilbert sorting are also similar.
Both implementations are robust. However CGAL uses a dynamic floating point precision approach (like explained here) while the Julia implementation uses floating point filtering. The floating point filtering in my implementation require all point coordinates to be in the range 1.0 .. 2.0, a restriction CGAL does not have, but only a minor annoyance in my view. See here for an explanation of this filtering method.
There are other difference in data sctructures. For e.g. I save a few calculations inside each triangle for fast predicate execution, and I chose not to store a pointer to the index of opossing points inside adjacent triangles. I don;t know if CGAL does the same. Most probably not.
Julia implementation uses about 2-3x the memory of CGAL. I'm not sure why, maybe the GC, maybe the different data-structures.
Not yet, but it will be. The code currently is fast but very rough. I'm sure some macros would help. There are many things to do, for e.g.:
- 3D Delaunay
- more generic datatypes
- Many helper functions (for iteration, etc.)
Note that 2D AND 3D predicates are currently working. So I would say about 20% of the work of implementing a 3D Delaunay construction algorithm is already done
It is fun writing Julia. I changed data structures and algorithms with ease. I don't think I could have done this with the same ease using C++. Also installing CGAL was not easy.
Cool!