4 ms·

> For most of my Voronoi map generation projects, I don’t actually use Voronoi, but something similar. I move the points from the circumcenters to the centroids

> For most of my Voronoi map generation projects, I don’t actually use Voronoi, but something similar. I move the points from the circumcenters to the centroids. Not only is this cheaper to calculate, it ensures that all the region edges have a reasonable length. With Voronoi, some of the edges have small or zero length, and that makes it harder for me to place roads and rivers using those edges. I have written more about this topic here. He is basically doing a form of relaxatation similar or equivalent to Lloyd's Algorithm[0], no? Adrian Secord used this way back in 2002 already to create stippling images[1], see also Mike Bostock's notebook[2]. Would iterating a few times maybe improve results even more? Tangent: I have been experimenting on and off with implementing more advanced variants of Secord's stippling algorithm in the past two weeks[3]. It's been a lot of fun! A bit too much at times, Observables makes the interactive feedback loop a bit too easy. [0] https://beta.observablehq.com/@mbostock/lloyds-algorithm https://beta.observablehq.com/@mbostock/lloyds-algorithm [1] https://cs.nyu.edu/~ajsecord/msc_thesis/ajsecord_msc_thesis.pdf https://cs.nyu.edu/~ajsecord/msc_thesis/ajsecord_msc_thesis.... [2] https://beta.observablehq.com/@mbostock/voronoi-stippling https://beta.observablehq.com/@mbostock/voronoi-stippling [3] https://beta.observablehq.com/@jobleonard/untitled https://beta.observablehq.com/@jobleonard/untitled (Yes, that still needs a lot of optimization. I know)

thrower123 8y ago
Yep, he is using a form of Lloyd relaxation, as detailed in the original polygonal map generator article http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...
mxfh 8y ago
Philippe Rivière did quite a number of iterations[1] on d3/Bostock's geo-voronoi, culminating in a proposed Voronoi Projection method[2]. [1]https://beta.observablehq.com/collection/@fil/voronoi https://beta.observablehq.com/collection/@fil/voronoi [2]https://projet.liris.cnrs.fr/mi2/posts/2018/10/05/voronoi-projection-en.html https://projet.liris.cnrs.fr/mi2/posts/2018/10/05/voronoi-pr...
- vanderZwan 8y ago
  Oh wow, thanks! I missed those. Will look into it - maybe he has optimizations I missed and vice versa. If only Observables had something like pull requests and a way to have meta-discussions on notebooks... but it's addictive enough an environment as is ;) EDIT: He even has a Spherical Lloyds Relaxation sketch[0], how appropriate! :D [0] https://beta.observablehq.com/@fil/spherical-lloyds-relaxation https://beta.observablehq.com/@fil/spherical-lloyds-relaxati...
dahart 8y ago
> He is basically doing a form of relaxatation similar or equivalent to Lloyd's Algorithm[0], no? Yes, this is one iteration of Lloyd’s algorithm. > Would iterating a few times maybe improve results even more? Yes, it would. Even one more iteration will help, the first steps tend to be the largest, and they usually get smaller and smaller until nearly converged. One interesting property of Lloyd’s algorithm, though, is that steps don’t get monotonically smaller. If you try to wait for true convergence, sometimes you’ll see large jumps many hundreds of iterations into the simulation. It can be a bit surprising to watch a point jump after all the points have been sitting very still for a while.
amitp 8y ago
It's similar, but the purpose is different. With Lloyd Relaxation you move the Voronoi seed points (input), and then regenerate Voronoi. What I'm doing here is moving the Voronoi vertices (output) from the circumcenters to the centroids. There's no iteration here because the input points don't move. Instead, I am constructing a non-Voronoi tesselation. It has the same structure as the Voronoi cells but the cells do not have the Voronoi property. For my map generator I don't need the Voronoi property; I needed other properties, which the centroid approach seems to give me.

thrower123 8y ago

Yep, he is using a form of Lloyd relaxation, as detailed in the original polygonal map generator article http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/ http://www-cs-students.stanford.edu/~amitp/game-programming/...

mxfh 8y ago

Philippe Rivière did quite a number of iterations[1] on d3/Bostock's geo-voronoi, culminating in a proposed Voronoi Projection method[2]. [1]https://beta.observablehq.com/collection/@fil/voronoi https://beta.observablehq.com/collection/@fil/voronoi [2]https://projet.liris.cnrs.fr/mi2/posts/2018/10/05/voronoi-projection-en.html https://projet.liris.cnrs.fr/mi2/posts/2018/10/05/voronoi-pr...

vanderZwan 8y ago
Oh wow, thanks! I missed those. Will look into it - maybe he has optimizations I missed and vice versa. If only Observables had something like pull requests and a way to have meta-discussions on notebooks... but it's addictive enough an environment as is ;) EDIT: He even has a Spherical Lloyds Relaxation sketch[0], how appropriate! :D [0] https://beta.observablehq.com/@fil/spherical-lloyds-relaxation https://beta.observablehq.com/@fil/spherical-lloyds-relaxati...

dahart 8y ago

> He is basically doing a form of relaxatation similar or equivalent to Lloyd's Algorithm[0], no? Yes, this is one iteration of Lloyd’s algorithm. > Would iterating a few times maybe improve results even more? Yes, it would. Even one more iteration will help, the first steps tend to be the largest, and they usually get smaller and smaller until nearly converged. One interesting property of Lloyd’s algorithm, though, is that steps don’t get monotonically smaller. If you try to wait for true convergence, sometimes you’ll see large jumps many hundreds of iterations into the simulation. It can be a bit surprising to watch a point jump after all the points have been sitting very still for a while.

amitp 8y ago

It's similar, but the purpose is different. With Lloyd Relaxation you move the Voronoi seed points (input), and then regenerate Voronoi. What I'm doing here is moving the Voronoi vertices (output) from the circumcenters to the centroids. There's no iteration here because the input points don't move. Instead, I am constructing a non-Voronoi tesselation. It has the same structure as the Voronoi cells but the cells do not have the Voronoi property. For my map generator I don't need the Voronoi property; I needed other properties, which the centroid approach seems to give me.