3 ms·
Show HN: Any dimensional Delaunay triangulation in JavaScript
- thomasahle 12y agoThe 2d demo works very nicely in my browser (Chrome 39), the 3d ( http://mikolalysenko.github.io/delaunay-triangulate/3d.html 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?
- 33a 12y agoThanks! 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.