Wow, I wish that this was around a year and a half ago. I was working on a pet project of mine to do finite element analysis on PCB Gerber files. One of the biggest stumbling blocks that I ran into was taking a 2D image parsed from a Gerber (side note: Gerber files have a really wacky yet interesting format and structure) and triangulating it. I had wanted to use DT to clean up edges and thin traces in the model but I just couldn't seem to grasp it, as interesting as the math was. It's a shame that I never finished it, maybe I will need to get back to it one of these days.
Visualizing Delaunay Triangulation
21–24 of 24 posts
Re: Visualizing Delaunay Triangulation
#22The Delaunay tree link in footnote 14 doesn’t work. But in any case you can build and incrementally update an AABB tree of the triangles to efficiently find the triangle containing query points, right? Though you need to rebuild the AABB tree if it gets too unbalanced.
Ah, thanks; updated the link.
Re: Visualizing Delaunay Triangulation
#23Great article! How does this algorithm compare to others, e.g. sweep algorithms like the one used by delaunator[0]? An obvious difference is sweep algorithms sort the points in some way before adding them, is that a key to efficiency gains? 0: https://github.com/mapbox/delaunator/blob/main/README.md#pap...
(Author here). I don't know enough about computational geometry to say anything intelligent here, but there has been a lot of progress in triangulation since 1985. The algorithm described here wasn't even state-of-the-art back then in the case that all your points are known up-front -- Guibas & Stolfi describe a separate O(nlog(n)) algorithm that also starts by sorting, and which can be parallelized, unlike the incremental approach. The sweep-hull algorithm doesn't seem parallelizable, but I have not actually read the papers so take that with a grain of salt.
Re: Visualizing Delaunay Triangulation
#24This is astounding! I’ve looked into papers on this topic before and found them indescipherable. I love the clean visualizations, the implementations, and the clear progression.