Show HN: Any dimensional Delaunay triangulation in JavaScript

github.com

2 points33a2 comments

The 2d demo works very nicely in my browser (Chrome 39), the 3d ( http://mikolalysenko.github.io/delaunay-triangulate/3d.html ) doesn't seem to do anything?

Nicely done anyhow! Not an easy thing to implement. What complexity does it run at?

Thanks! The algorithm is based on Clarkson's incremental convex hull algorithm and runs in O(n^ceil(d/2) + n log(n)). I am planning on eventually adding a special case for d=2 to use a sweep line method, which is faster in practice.

Also note that all internal computations are performed using exact arithmetic based on Shewchuk's filtered predicates.

Reply on news.ycombinator.com