Voronoi ( Fortune’s algorithm ) slide show set to Dorime chipmunk (Ameno by Era) – why that song? it was handy and easy to synchronize.
Music Source: https://www.youtube.com/watch?v=qQ3ZVmXNgt0
Slides source: http://ima.udg.es/~sellares/ComGeo/
Oh it’s definitely on my list. But I’m going to see this through until I really deeply understand the sweep line algorithm for voronoi. I understand it in its gist but I’m fascinated by the various floating point problems implementers have with it and such.
But – look OpenVoronoi
Just now I found a slideshow so I set it to music I had hanging around me in hopes that I’ll watch it a few times, pause as I go and ‘get it’ a little better.
I think it’s possible to utilize this sweep line as a metaphor for problem solving if it’s working the way I think it does. But I have to be sure.
What’s fascinating to me about Fortune’s algorithm is that it _doesn’t_ backtrack in its own history. It keeps moving forward while constructing boundaries.
I think there’s a way to do it on pen and paper and I may try later. ‘m still returning back to this (Fortune’s algorithm) when I can through the day. It’s definitely an object of meditation for me.
There’s something in mathematical morphology that this is reminding me of… oh gosh.. what is it… the dots are mountain regions…. and the valleys are the edges of the voronoi graph…
mountains and valleys… water rushing through…
It’s the segmentation problem. Watershed! knew I’d seen it in mathematical morphology. There should be a comparison somewhere between it and voronoi.
YES. Voronoi is one of THREE common ways to do a 3D Watershed.
a) Splitting, which uses distance map. [bigger objects are rated as higher]
b) Voronoi, which computes zones between objects
c) Segmentation, which uses the gradient of the images, particularly the edges of the grayscale image.
I’m going to work on hand-drawing later I think though,. I’m pretty sure I saw a video of a professor doing just that in my travels.
A few more posts as I’m on “sweep line algorithms” right now [part of computational geometry].
(1) closest pair in the planar point set
🔊 Listen to this