Visualizing Delaunay Triangulation

#1

Post by ianthehenry » Mon, Jul 11, 2022, 3:12 PM UTC

Visualizing Delaunay Triangulation
ianthehenry.com

Re: Visualizing Delaunay Triangulation

#2

Post by zackoverflow » Mon, Jul 11, 2022, 3:55 PM UTC

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

Re: Visualizing Delaunay Triangulation

#3

Post by ianthehenry » Mon, Jul 11, 2022, 5:17 PM UTC

zackoverflow wrote: post #2

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

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

Re: Visualizing Delaunay Triangulation

#4

Post by pragmatic8 » Mon, Jul 11, 2022, 11:36 PM UTC

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.

Re: Visualizing Delaunay Triangulation

#5

Post by danielEM » Tue, Jul 12, 2022, 2:45 AM UTC

This is type of HN I enjoy! Thanks!

Re: Visualizing Delaunay Triangulation

#6

Post by evouga » Tue, Jul 12, 2022, 11:37 PM UTC

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.

Re: Visualizing Delaunay Triangulation

#7

Post by munificent » Wed, Jul 13, 2022, 12:41 AM UTC

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

Re: Visualizing Delaunay Triangulation

#8

Post by im3w1l » Wed, Jul 13, 2022, 1:11 AM UTC

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.

Re: Visualizing Delaunay Triangulation

#9

Post by jbay808 » Wed, Jul 13, 2022, 2:07 AM UTC

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.

Re: Visualizing Delaunay Triangulation

#10

Post by bavell » Wed, Jul 13, 2022, 2:16 AM UTC

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