Voronoi Graph

Before we will start to generate something looks like a map we need to understand what is the map and decide what method we are going to use to generate it. Simplifying,  the map is the two-dimensional representation of the surface of the world. The main thing that allows us to say whether this image is map or not is the obvious partition between land and water masses. To have an ability to divide a canvas into land and water we need to know what pieces are lower that others, it means we need to generate a heightmap.

There are three main ways to generate a heightmap: use noise function, use graph structure, or use both. I believe a clear noise terrains looks a bit artificial, so the better way for a maps tending to have plausible look is to use graph structure. Thankfully, there is an excellent tutorial by Amit Patel, so we don’t have to re-invent the wheel. As you can see from Amit’s demo, even a square or hex graphs look fine, but really good result could be achieved only with relaxed Voronoi diagram. Please read the Amit’s tutorial first if you don’t familiar with Voronoi diagrams, as I won’t explain the theory which I understand only in basics.

One more luck, generating Voronoi diagrams in javascript is really easy. You just need to use D3.voronoi implementation of Fortune’s algorithm by Mike Bostock. D3 is a really great visualization framework, just look through the Mike’s examples. Please note I’m not a D3 expert and my code contains redundant lines and errors.

Lets generate a simple set of 100 Voronoi polygons (FSFiddle for the code below):

var svg = d3.select("svg"),
  width = +svg.attr("width"),
  height = +svg.attr("height"),
  sites = d3.range(100).map(function(d) {
    return [Math.random() * width, Math.random() * height];
  }),
  voronoi = d3.voronoi().extent([[0, 0], [width, height]]),
  diagram = voronoi(sites), polygons = diagram.polygons(); 

// Draw the polygons
polygons.map(function(i) {
  svg.append("path")
    .attr("d", "M" + i.join("L") + "Z");
});

100 Voronoi polygons

I rendered only polygons (cells), but it is easy to draw sites (points), edges or corners (see Amit’s article for the details). As you can see random points tessellation is a little bit irregular. We can improve it using the Lloyd Relaxation. And again, it is really easy to do with D3.

Set of 100 Voronoi relaxed polygons (FSFiddle):

var svg = d3.select("svg"),
  width = +svg.attr("width"),
  height = +svg.attr("height"),
  sites = d3.range(100).map(function(d) {
    return [Math.random() * width, Math.random() * height];}),
  voronoi = d3.voronoi().extent([[0, 0], [width, height]]),
  relaxedSites = voronoi(sites).polygons().map(d3.polygonCentroid),
  diagram = voronoi(relaxedSites),
  polygons = diagram.polygons(); 

// Draw the polygons
polygons.map(function(i) {
 svg.append("path").attr("d", "M" + i.join("L") + "Z");
});

100 Voronoi polygons (relaxed)

Much better! We can try to add one more iteration of Lloyd relaxation, but I don’t think it’s necessary. It takes some time with kilos of points, but improvement is not so significant. You may compare the iterations results in process (JSFiddle):

You probably think 2 iterations looks much better than 1. Is it so, but the difference won’t be obvious in close-to-real generation. Let’s increase the point count up to 1000 and add some colors (FSFiddle):

var svg = d3.select("svg"),
  width = +svg.attr("width"),
  height = +svg.attr("height"),
  sites = d3.range(1000).map(function(d) {
    return [Math.random() * width, Math.random() * height];
  }),
  voronoi = d3.voronoi().extent([[0, 0],[width, height]]),
  diagram = voronoi(sites), polygons = diagram.polygons(),
  // Add spectral color range[0,1] using d3-scale-chromatic
 color = d3.scaleSequential(d3.interpolateSpectral); 

// Draw the colored polygons
polygons.map(function(i, d) {
  svg.append("path")
.attr("d", "M" + i.join("L") + "Z")
.attr("fill", color(d/1000));
});

// Adding relax function
function relax() {
  iteration.value = +iteration.value + 1;
  svg.selectAll("path").remove();
  sites = voronoi(sites).polygons().map(d3.polygonCentroid);
  diagram = voronoi(sites);
  polygons = diagram.polygons(); 

  // Redraw polygons after relaxation
  polygons.map(function(i, d) {
    svg.append("path")
      .attr("d", "M" + i.join("L") + "Z")
      .attr("fill", color(d/1000)); });
  }

Not rexaled

Relaxed (1 iteration)

Relaxed (2 iterations)

After some time, introducing a new feature, I realized the 1 iteration is not enough for a things like path-finding or a polygon-based drawing. Produced grid is too irregular and we need up to 20 Lloyd’s iterations to make it easy to use. The solution came to my mind is to begin not with just a random set of sites, but a kind of intelligible algorithm, that with produce more regular grid by itself, without any relaxation. Hopefully, there is a Poisson-disc sampling algorithm, realized in js by Jason Davies. And even more, D3 creator Mike Bostock had implemented the algorithm on D3, so the can just take the code as is with all the regards to its creators.

Now we need to understand what data is provided by D3.voronoi and what data do we need for a map generation. There are two major possibilities: use Voronoi polygons themselves, or use the Delaunay triangulation (triangles with vertices at the polygons sites). From the current experience I can state that the best variant is to use both of them, but as of now my generator ignores triangulation and works with Voronoi polygons only.

To use the Voronoi polygons we need to know three things for each and every polygon:

• site coordinate (base polygon point)
• edges coordinates (they form polygon shape)
• reference to neighbors (to interact with other polygons)

Let’s see what data D3 provides for diagram.polygons object:

console.table(diagram.polygons()[0]);

0-5 gives us edges coordinates; data contains site coordinates. Not bad, but not enough. Let’s check two more objects, diagram.cells and diagram.edges:

console.table(diagram.cells[0]);
console.table(diagram.edges[diagram.cells[0].halfedges[0]]);

As you can see diagram.cells contains site coordinates, reference to polygon (index) and references to polygon edges (halfedges). Using the halfedges we can restore the references to the polygon neighbors as its indexes.

As it’s much more convenient to have all needed data at one place let’s update out relax function to use the same loop to collect the data and add as attributes to diagram.polygons object (FSFiddle):

function relax() {
  // relaxation itself
  iteration.value = +iteration.value + 1;
  svg.selectAll("path").remove();
  sites = voronoi(sites).polygons().map(d3.polygonCentroid);
  diagram = voronoi(sites);
  polygons = diagram.polygons();

  // push neighbors indexes to each polygons element
  polygons.map(function(i, d) {
    i.index = d; // index of this element
    var neighbors = [];
    diagram.cells[d].halfedges.forEach(function(e) {
      var edge = diagram.edges[e], ea;
      if (edge.left && edge.right) {
        ea = edge.left.index;
        if (ea === d) {
          ea = edge.right.index;
        }
        neighbors.push(ea);
      }
  })
  i.neighbors = neighbors;
  svg.append("path")
    .attr("d", "M" + i.join("L") + "Z")
    .attr("fill", color(d/1000));
  });
  // show 1st array element in console
  console.log(polygons[0]);
}

Now we got a scalable Voronoi graph and can proceed with heights definition. This crucial problem will be covered in the next post.