Voronoi Tessellations(datagenetics.com)
datagenetics.com
Voronoi Tessellations
http://datagenetics.com/blog/may12017/index.html
19 comments
(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
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
Thanks for the quick fix; I quite enjoyed the writeup.
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
Speaking of attribution, why doesn't that article reference Lloyd's algorithm? https://en.m.wikipedia.org/wiki/Lloyd%27s_algorithm
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...
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...
Glad to hear it! FWIW, you are using Lloyd's algorithm and the first paper is too ([1] mentions Lloyd 7 times so it's unclear why they didn't put his paper in the references section, that seems like an oversight.)
Nothing wrong with using the Wikipedia article as an informal reference, but wherever you reference the other papers, considering linking to Lloyd's IEEE paper directly.
Splitting the centroid computation into a two-pass accumulation is a great idea. Even though that makes for heavy shaders, I imagine it's still faster than doing a buffer read and finding the centroids in one pass via CPU?
I'd also be interested in hearing how you decide on convergence. Are you stoppping after a fixed number of iterations? Or are you able to track the offsets using the GPU - not sure if that is possible since you're writing back into the VBO directly? You probably know from playing with it that Lloyd's algorithm is notorious for very long convergence times. It gets close very quickly, and then can have a super long tail with many small iterations and then sudden large changes long after it seemed like things had settled. It's super fun to watch, especially when you dynamically add points, very reminiscent of cell division -- you should make a video for your project page!
You might be interested in this paper too: http://www.dgp.toronto.edu/papers/ahausner_SIGGRAPH2001.pdf This one uses GPU Voronoi + Lloyd's algorithm to generate mosaic tilings. The neat trick here is to use a Manhattan distance instead of a Euclidean one, in order to get voronoi cells to line up in mostly rectangular grids instead of approximating a hexagonal packing.
Nothing wrong with using the Wikipedia article as an informal reference, but wherever you reference the other papers, considering linking to Lloyd's IEEE paper directly.
Splitting the centroid computation into a two-pass accumulation is a great idea. Even though that makes for heavy shaders, I imagine it's still faster than doing a buffer read and finding the centroids in one pass via CPU?
I'd also be interested in hearing how you decide on convergence. Are you stoppping after a fixed number of iterations? Or are you able to track the offsets using the GPU - not sure if that is possible since you're writing back into the VBO directly? You probably know from playing with it that Lloyd's algorithm is notorious for very long convergence times. It gets close very quickly, and then can have a super long tail with many small iterations and then sudden large changes long after it seemed like things had settled. It's super fun to watch, especially when you dynamically add points, very reminiscent of cell division -- you should make a video for your project page!
You might be interested in this paper too: http://www.dgp.toronto.edu/papers/ahausner_SIGGRAPH2001.pdf This one uses GPU Voronoi + Lloyd's algorithm to generate mosaic tilings. The neat trick here is to use a Manhattan distance instead of a Euclidean one, in order to get voronoi cells to line up in mostly rectangular grids instead of approximating a hexagonal packing.
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!
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.
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.
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?
You can create these easily using SQL, Postgres, & PostGIS.
https://postgis.net/docs/ST_VoronoiPolygons.html
https://postgis.net/docs/ST_VoronoiPolygons.html
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
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
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
If you generate a Voronoi tesselation for a set of points, you can then merge neighboring areas to create isoclines
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.
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
[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
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
> 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
That's how it's done in QHull, the basis for SciPy's voronoi features.
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
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...
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...
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.
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.
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 :-)
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 :-)
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
I wrote a paper on it long ago, the third one listed here if you're interested
http://chofter.com/masters.php
Here is a fullscreen Voronoi made by Neave.
https://neave.com/voronoi/
https://neave.com/voronoi/
Good (visual) explanation!
Voronoi helped us once to make a game: https://www.airconsole.com/play/multiplayer-games/polyracer
Voronoi helped us once to make a game: https://www.airconsole.com/play/multiplayer-games/polyracer
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
/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
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
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.
Check out http://www.quantize.maths-fi.com/
The website is edited by some of the best mathematicians in numerical probability field.
[deleted]
These are also used to create the mesh for computational fluid dynamics.
Anybody used catmull-clark on top of voronoi ? Just curious.
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/