Visualizing Delaunay Triangulation

by ianthehenry • 4 years ago

176 23 4 years ago

Really entertaining read, had a few laughs throughout! but for some reason the text doesn't fracture properly on Brave/Chrome.

Here's a video demonstrating the problem: https://anno.so/71yMRyQfDXnm0QoHNpT6d/1

ianthehenry3• 4 years ago

Haaaah. Oh that's a nightmare. Thanks! I think I fixed it in a portable way...

pragmatic8• 4 years ago

Thanks for writing this article. I tried to implement this algorithm a few years ago, but had trouble wrapping my head around the quad edge data structure.

danielEM• 4 years ago

This is type of HN I enjoy! Thanks!

evouga• 4 years ago

The 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.

ianthehenry3• 4 years ago

Ah, thanks; updated the link.

munificent• 4 years ago

I love everything about this. The content is interesting, the writing style is excellent, and the graphics are just adorable.

im3w1l• 4 years ago

Implementing the Delaunay Triangulation was my first task on my first programming job. Good memories. Spent way too much time over-engineering it against degenerate cases and floating point issues. And then in the end I think it never ended up in production.

jbay808• 4 years ago

This is very helpful. I'm using Delaunay triangulation on a project (implemented by a 3rd party library) and this really helps understand the natural data structure to use when doing manipulations. Much better than my own naive attempt, which ran into the exact mess that the author described.

bavell• 4 years ago

Underrated post, great article! Really makes me want to spend a weekend tinkering with math visualizations :)

mbrodersen• 4 years ago

What an excellent read. Content like that is why I read HN.

muti• 4 years ago

Great 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...

ianthehenry3• 4 years ago

(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.

greggman3• 4 years ago

This is amazing! Thank you!

I wanted to point out that using `image-rendering: pixelated` ends up with extremely ugly diagrams if, like me, you're on a machine with a non-integer devicePixelRatio.

https://i.imgur.com/X3Xy4CE.png

Note: There's no way display an image in a browser 1x1 pixels, nor 1xN where N is an integer, without JavaScript. Say like your page, you set the canvas 768px, and you set its resolution to 384x256, Well on my machine with a devicePixelRatio of 1.3333333730697632 that means the requested display size 768px becomes 1024 devicePixels. 384 doesn't divide 1024 evenly and with `image-rendering: pixelated` that means every few src pixels is 3 pixels wide instead of 2.

Anyway, solutions:

1. Don't pixelate, instead go the other way, increase the resolution of the canvas and use scale or whatever other techniques to get smooth lines

2. Use JS to adjust the display size of the canvas so that it's some multiple of device pixels

Here's library for that: https://greggman.github.io/pixel-perfect.js/

Still not fully perfect because MacOS hides the true resolution of the display from apps but generally still ok as MacOS goes out of it's way to look good even with scaling.

johndough• 4 years ago

For anyone wondering about the odd number, 1.3333333730697632 is (double)((float)1440 / 1080)). The exact value would be 1440 / 1080 = 1.333... (continued).

Gordonjcp• 4 years ago

I'm running into this a lot with DaVinci Resolve at the moment, which doesn't believe that 720x576 16:9 with nonsquare pixels is a thing.

vvrm• 4 years ago

+1 Awesome introduction to computational geometry. Couldn’t help but mention this fun fact: Voronoi diagrams were used to fight the 1854 Cholera outbreak in London

https://plus.maths.org/content/uncovering-cause-cholera

shimonabi• 4 years ago

I have actually implemented the quad-edge structure and the algorithms from this paper in Python for my undergraduate class.

The problem was when I tried to explain my professor how the thing actually works on an example. The abtract math is very heavy. I barely managed to pass the class.

larodi• 4 years ago

Kudos for such a great article with multidisciplinary references all over!

amelius• 4 years ago

If you really want a great mesh with some guaranteed properties, not just a Delaunay triangulation (which can still contain small angles), look into the work of Jonathan Shewchuk.

For example, for 2d mesh generation:

http://www.cs.cmu.edu/~quake/triangle.demo.html

He also solved the problem of degenerate cases (e.g. four vertices exactly on a circle) with adaptive precision floating point arithmetic.

TuesdayNights• 4 years ago

This was a great read! I've found triangulation so captivating, and I think it's because the word sounds like something made up from some James Bonds like movie.

I first learned about Delaunay Triangulation from a talk by a lead developer (James Anhalt, who is now at Frost Giant Studios) on Starcraft 2's pathing. https://www.gdcvault.com/play/1014514/AI-Navigation-It-s-Not The talk is on the older side now, but I still find it insightful. SC2 is over 12 years and its pathing is still considered the gold standard for RTS games. The SC2 Map editor will show the triangulation for a given map, which provided me a nice visualization when learning this topic. (in the map editor it's called "enable pathing mesh".)

theduemmer• 4 years ago

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.

Mageek• 4 years ago

This 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.

Visualizing Delaunay Triangulation

Related Stories