Voronoi Tessellations

http://datagenetics.com/blog/may12017/index.html

by sebg • 9 years ago

158 29 9 years ago

Jack000• 9 years ago

the point + line generalized Voronoi diagram is also related to the medial axis, which is used for calculating offsets in CNC applications:

https://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html

you need the medial axis for v-carving, to control the CNC like so: https://youtu.be/jJhaDHmXvsY?t=1m15s

pacaro• 9 years ago

Interesting reading the different methods for creating the Voronoi tesselation. I've always built the Delaunay triangulation first, I guess I knew there were other approaches, just never bothered to find out what.

If you generate a Voronoi tesselation for a set of points, you can then merge neighboring areas to create isoclines

cromulent• 9 years ago

You can create these easily using SQL, Postgres, & PostGIS.

https://postgis.net/docs/ST_VoronoiPolygons.html

shane_dw• 9 years ago

Here is a fullscreen Voronoi made by Neave.

https://neave.com/voronoi/

Zeustastic• 9 years ago

Good (visual) explanation!

Voronoi helped us once to make a game: https://www.airconsole.com/play/multiplayer-games/polyracer

agumonkey• 9 years ago

Anybody used catmull-clark on top of voronoi ? Just curious.

tlrobinson• 9 years ago

Voronoi tessellations are common in data visualizations to increase the size of click/hover targets and to position labels. It's built into d3: https://github.com/d3/d3-voronoi

catwell• 9 years ago

Voronoi tesselation is also a step in K-Means, which is one of the most well-known clustering algorithms (typically used for quantization). Here is a page with an interactive visual example for it: https://www.naftaliharris.com/blog/visualizing-k-means-clust...

Note that the DataGenetics article talks about 2D Voronoi cells but they (and K-Means as well) can be generalized to a space of any dimensionality.

JohnStrange• 9 years ago

They are also used for Conceptual Spaces in cognitive science and semantics. I wonder what's the most efficient visualization algorithm for k-dimensions when a set of central points is provided. Is it Fortune's algorithm or are there faster ones?

FreeFull• 9 years ago

The article mentions Delanuay triangulation, but it doesn't mention that one way to calculate a Voronoi tesselation is to calculate the Delanuay triangulation first.

jayrhynas• 9 years ago

It does however mention going the other way:

If you create a dual graph of a Voronoi diagram (connect each node to every other node that shares an edge), you end up with a graph that is a Delaunay Triangulation

btschaegg• 9 years ago

Interestingly, the reverse as also very true: A simple and rather effective method to calculate a delaunay triangulation on a set of 2D points on a GPU is to actually calculate the according Voronoi diagram (discretely) into a texture (using jump flooding) and handling the edges between the cells[1][2].

[1] http://www.cs.utah.edu/~maljovec/files/DT_on_the_GPU_Print.p...

[2] http://www.comp.nus.edu.sg/~tants/delaunay/GPUDT.pdf

philipov• 9 years ago

That's how it's done in QHull, the basis for SciPy's voronoi features.

ktzar• 9 years ago

I did a while ago a simple implementation of k-means in Javascript, it shows how the process converges for cluster finding. http://ktzar.github.io/js-k-means-clustering/ code: https://github.com/ktzar/js-k-means-clustering

teddyh• 9 years ago

/usr/lib/xscreensaver/voronoi

man voronoi:

“This implementation takes advantage of the OpenGL depth buffer to compute the cells for us, by rendering the intersection of overlapping cones in an orthographic plane.”

https://www.youtube.com/watch?v=hD_8cBvknUM

rq1• 9 years ago

Check out http://www.quantize.maths-fi.com/ The website is edited by some of the best mathematicians in numerical probability field.

nissimk• 9 years ago

Marc DiMarco gave really entertaining presentation on user interface algorithms at acm applicative conference a couple of years ago including covering the voronoi diagram.

I think this is an earlier version of the same presentation

https://youtu.be/8_75wViQQY8

It was interesting to hear about the use by an early epidemiologist to find the bad water source during the cholera outbreak in London.

kgilpin• 9 years ago

These are also used to create the mesh for computational fluid dynamics.

mkeeter3• 9 years ago

I find it particularly interesting that this post steals images from my blog [1], then adjusts the saturation / brightness on them so that a reverse image search thinks they are unique.

Please don't do this. Folks put effort into well-illustrated explanations; if you're going to re-use content, at least put an attribution and link on there!

[1] http://www.mattkeeter.com/projects/swingline/

heydenberk• 9 years ago

That's incredibly frustrating and also just ... dumb? I wouldn't have thought any less of the post if it had cited a different interesting post. I would've liked it more, even!

dahart2• 9 years ago

You're well within reasonable bounds to request that they be removed or ask for an attribution. If you created those images, they are covered by copyright, and their use of those images without permission is a copyright violation.

Speaking of attribution, why doesn't that article reference Lloyd's algorithm? https://en.m.wikipedia.org/wiki/Lloyd%27s_algorithm

mkeeter3• 9 years ago

I'm not familiar, but from a quick review it looks like Lloyd's algorithm is a few citations down the chain. I started from [1], which is based on [2], which uses Lloyd's algorithm (check out the Related Work section in the first paper).

Still, that's a good stand-alone link – I'll add it to the writeup.

[1] https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord... [2] https://www.cs.princeton.edu/courses/archive/fall00/cs597b/p...

squeakynick• 9 years ago

(Author here)

Matt, I'm very sorry. It was a genuine mistake. I always try hard to attribute sources (as you can see from the references in the doc, and on the couple of hundred other articles on my blog). It was nothing personal, it was an oversight :)

I've corrected this now on the site. Sorry again. Thanks for bringing this to my attention.

Regards

/\/ick

mkeeter3• 9 years ago

Thanks for the quick fix; I quite enjoyed the writeup.

sethammons• 9 years ago

I've seen a website background that looked like the shifting gif. Something fancy in js that some developer made. Looked really neat. Ate 100% of my CPU to look at their main site or blog, but it did look neat. Nice to get an idea of what they were doing.

DizzyDoo• 9 years ago

Voronoi diagrams are used a lot in game development too, in creating and recalculating navmeshes in games where the navigation graph changes often. I have a game project underway right now where the player can build fences, lampposts and other obstacles, and the hundred plus AI actors need to be able to navigate it in real-time. Recalculating the Delauney Triangulation and the Voronoi tessleation is expensive, so I just sent it to a thread, it's worthwhile to do all that work because A* pathfinding on anything other than a navmesh would be, for my project, incredibly slow. This sort of algorithm is a great thing to know that it exists and have in your backpocket.

EDIT: I have a little devlog about the game I'm developing full-time, back in October 2015 I made a video where I talked through the first pass of my Voronoi/Navmesh implementation. Might be worth watching if anyone wants to see the tesselation overlaid onto a game world, for a real-life usage of the algorithms: https://www.youtube.com/watch?v=zPD3HqI6HDE I should assure everyone that the game looks _very_ different now thought! No more checkerboard textures...

shaneos2• 9 years ago

If you're interested in building Voronoi and Delaunay graphs in C++, I wrote some easily reusable code years ago, a fixed up version of Stephen Fortunes algorithm.

http://chofter.com/mapviewer/voronoi.php

Pardon my pre-web-engineer lack of HTML knowledge, I was young and mind melded with robots at the time :-)

shaneos2• 9 years ago

Related, another cool thing that Voronoi graphs are useful for is enumeration all possible paths a robot can take in an environment. This can be used to determine the quality of the map built with sonar/radar/lidar, to better understand the value of a sensor or algorithm in SLAM.

I wrote a paper on it long ago, the third one listed here if you're interested

http://chofter.com/masters.php

Voronoi Tessellations

Related Stories