Graphics! Voronoi, Delaunay, Natural Neighbor - Code, Sound & Surround E03

Watch these beautiful animations to learn more about #Voronoi diagrams, #Delaunay triangulations, and natural neighbor #interpolation. Dynamic and colorful visuals give an intuitive feel for these processes, and step-by-step illustrations make the algorithms easy to follow in detail.
Partial video transcript:
blog.mikebourgeous.com/2021/0...
Code for these algorithms is on GitHub:
github.com/mike-bourgeous/mb-...
Timestamps:
0:00 Intro
1:07 Voronoi Partition Overview
2:18 Delaunay Triangulation Overview
3:42 Delaunay Triangulation Algorithm
8:53 Voronoi Partition Algorithm
10:41 Natural Neighbor Interpolation
15:26 Outro
Places to learn more:
en.wikipedia.org/wiki/Delauna...
en.wikipedia.org/wiki/Voronoi...
en.wikipedia.org/wiki/Natural...
en.wikipedia.org/wiki/Computa...
en.wikipedia.org/wiki/Multiva...
Delaunay triangulation paper: "Two algorithms for constructing a Delaunay triangulation" by Lee and Schachter: scholar.google.com/scholar?q=...

[@discreet_boson]

This channel is criminally underrated

[@NickWaanders]

Great explanations and visuals! This video deserves many more views.

[@tl880linux]

Thanks!

[@ArthMaxim]

Excelent work : arts + math + code + music !

[@vector8310]

THIS has been up for 2 years yet it's only now that the yt algorithm suggested it?
Brilliant work!

[@tl880linux]

Thank-you!

[@TheArgon14]

Reminds me of my Graph Theory class back in college, awesome to see it all in practice!

[@briantriesart]

This video is amazing. Thank you very very much!

[@emanuelgerber]

Super helpful video! Thank you

[@baronvonbeandip]

Commenting for the algorithm

[@Michallote]

This is amazing. Great work bro. You earned a sub

[@SHOPETSY]

Great video… 😊. Thanks 🙏🏼

[@redwavez3436]

Great video

[@Koldora]

Beautifully visualized; well paced; with great production quality. Wish you and your channel continued success.

[@tl880linux]

Thank you! Your Voronoi diagram videos were also helpful.

[@bbourgeous]

Excellent animations. Your explanations are so much clearer than how I learned it.

[@tl880linux]

Thanks! My hope is that these videos spark ideas for new places to apply these concepts, by making them seem more relatable and useful.

[@coralmillenium]

Phenomenal video!👏👏👏 Thank you!

[@tl880linux]

Thanks!

[@ian.ambrose]

This is my first time seeing someone having both advanced knowledge of math and music theory at the same time.

[@yu_a_vi4427]

this a gem lost to yt algorithm

[@Broadsmile1987]

Very nice video, though at moments rushed.

[@victoroliari9479]

Great video, very elucidative.
I was so into it that I would like to read the algorithm description. Could you share the name of the papers you cited in the video?

[@tl880linux]

Thanks, and thanks for the question!
I referenced the O(n log n) algorithm from "Two algorithms for constructing a Delaunay triangulation" by Lee and Schachter for triangulation. Google Scholar has a link to a PDF. For Voronoi conversion and natural neighbor interpolation I just used the descriptions from their Wikipedia articles.
I thought this paper was in the description already so I will add it there too.

[@rocklobster1976]

Omg.... Where have you been my whole life?
YOU'RE HIRED!!

[@hardtofinduniquename]

At 2:46:
> every edge of a delaney triangle is perpendicular to an edge of a voronoi polygon
It took me a while to see it, but these perpendicular edges don't necessarily intersect. FH is perpendicular to the top right edge in H and not the edge that it crosses.

[@tl880linux]

That's a really good point! That perpendicular line is always there, but it might not be obvious which one it is. Another example is edge DI.

[@edwardoakheart4055]

Great video, just have one question, how do you find the next vertex when finding the lower tangent in the merge part?

[@tl880linux]

Great question! The Lee and Schachter paper describes a function they called "HULL" that finds the lower tangent. I translated that function into Ruby and reversed it to also find the upper tangent.
If I'm reading and remembering right, the "next" neighbor for the points in the current guess is considered from each hull, and the next point is chosen based on whether one of those neighbors is on the "wrong" side of the current guess for the lower tangent. Hope this helps!
Here's my code: github.com/mike-bourgeous/mb-geometry/blob/5e18eb910c182b99755b852f133f0b8579372884/lib/mb/geometry/delaunay_debug.rb#L75-L123

[@bakeer2018]

great video, can you tell what tools did you use to do this excelllent animation ?

[@tl880linux]

Thanks! It's custom software. Some of the animations render to SVG, most of them go through my custom visualization software using OpenGL. I edit the rendered video in VEGAS Pro. I released an open source command line tool for some of the simpler animations: github.com/mike-bourgeous/mb-geometry/blob/master/bin/voronoi_transitions.rb