What an excellent read. Content like that is why I read HN.
Visualizing Delaunay Triangulation
11–20 of 24 posts
Re: Visualizing Delaunay Triangulation
#12Great 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...
Re: Visualizing Delaunay Triangulation
#13This 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.
Re: Visualizing Delaunay Triangulation
#14This 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 3…
For anyone wondering about the odd number, 1.3333333730697632 is (double)((float)1440 / 1080)). The exact value would be 1440 / 1080 = 1.333... (continued).
Re: Visualizing Delaunay Triangulation
#15+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
Re: Visualizing Delaunay Triangulation
#16I 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.
Re: Visualizing Delaunay Triangulation
#17This 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 3…
For anyone wondering about the odd number, 1.3333333730697632 is (double)((float)1440 / 1080)). The exact value would be 1440 / 1080 = 1.333... (continued).
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.
Re: Visualizing Delaunay Triangulation
#18Kudos for such a great article with multidisciplinary references all over!
Re: Visualizing Delaunay Triangulation
#19If 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.
Re: Visualizing Delaunay Triangulation
#20This 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".)