Graphics! Voronoi, Delaunay, Natural Neighbor

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

Рет қаралды 10,144

Күн бұрын

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

Пікірлер: 30

@discreet_boson 2 жыл бұрын

This channel is criminally underrated

@NickWaanders 2 жыл бұрын

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

@tl880linux 2 жыл бұрын

Thanks!

@briantriesart 2 ай бұрын

This video is amazing. Thank you very very much!

@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!

@coralmillenium 5 ай бұрын

Phenomenal video!👏👏👏 Thank you!

@tl880linux 5 ай бұрын

Thanks!

@TheArgon14 3 жыл бұрын

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

@Michallote 5 ай бұрын

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

@emanuelgerber 8 ай бұрын

Super helpful video! Thank you

@ian.ambrose Жыл бұрын

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

@redwavez3436 5 ай бұрын

Great video

@SHOPETSY Жыл бұрын

Great video… 😊. Thanks 🙏🏼

@Koldora 2 жыл бұрын

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

@tl880linux 2 жыл бұрын

Thank you! Your Voronoi diagram videos were also helpful.

@bbourgeous 2 жыл бұрын

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

@tl880linux 2 жыл бұрын

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

@baronvonbeandip 8 ай бұрын

Commenting for the algorithm

@yu_a_vi4427 Жыл бұрын

this a gem lost to yt algorithm

@victoroliari9479 3 ай бұрын

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 3 ай бұрын

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.

@edwardoakheart4055 2 жыл бұрын

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

@tl880linux 2 жыл бұрын

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

@hardtofinduniquename 2 жыл бұрын

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 2 жыл бұрын

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.

@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