Skip to content

Instantly share code, notes, and snippets.

@katossky

katossky/.block

Forked from mbostock/.block
Last active February 16, 2021 01:52
Show Gist options
  • Save katossky/8db7ada3940163ac8969d0515c70b0c0 to your computer and use it in GitHub Desktop.
Save katossky/8db7ada3940163ac8969d0515c70b0c0 to your computer and use it in GitHub Desktop.
Download ZIP
A random algorithm for the map-coloring problem
Raw
.block
license: gpl-3.0
Raw
README.md

This map is adapted from Mike Bostock's world map with random colors. I implement an alternative algorithm for colouring the countries.

Original coloring algorithm

The principle for Mikes's coloring is:

  1. Take an ordered list of 10 colors
  2. Take a region and assign it the first color (blue) by default
  3. If the regions has neighbors, find out which is the highest ranked one in the list, and take the next one, which then necessarily different
  4. Repeat until all regions are filled

Here's what you get:

Mike Bostock's world map

This method works well for a world map but it has a few drawbacks:

  • All regions with no neighbors (i.e. islands: Greenland, Iceland, Japan, Australia...) get colored in blue whereas it would be more pleasant that they come in various colors
  • The first colors in the list get to dominate the map and some (grey) are virtually unused.
  • It is not obvious on the world map, but Mike's method may use a very high number of colors, clearly over 10! (In practice, the consequence is that his implementation loops back to the beginning of the color list so that adjacent regions may share colors.) Why is that so? Imagine a region with only one neighbor, colored after the last color in the list. Any colour but the last one can be used here, but Mike's method requires to take the color after the highest ranked color among neighbors. Since by hypothesis, this highest ranked color is already the last in the list, we have a problem.

Alternative algorithm

My proposed algorithm goes like this:

  1. Take an ordered list of 3 colours
  2. Take a region ; draw a random color from the list ; assign this color to that region by default
  3. If the region has neighbors, find out which colours are already in use among them ; if all colours are used, push a new colour to the list and fill the current region with it ; if not, pick a random colour among the colours not in use
  4. Repeat until all regions are filled

This algorithm can colour all the countries of the world map with between 6 and 7 colours.

Further improvements

  • This algorithm does not cope with the dominance of one colour over the others. The colors added late to the list are clearly dominated.
  • Colors given to big states (Russia, China...) give the impression to prevail.
  • The number of colours changes randomly.
  • The colouring itself is random, which may be problematic in some cases.

You're welcome to suggest improvements!

Data

This map shows the Natural Earth Admin 0 - Countries shapefile at 50m resolution. Converted to TopoJSON, only 140K gzipped. Each country is identified by its ISO 3166-1 numeric code.

Raw
index.html
<!DOCTYPE html>
<meta charset="utf-8">
<style>
body {
background: #fcfcfa;
}
.stroke {
fill: none;
stroke: #000;
stroke-width: 3px;
}
.fill {
fill: #fff;
}
.graticule {
fill: none;
stroke: #777;
stroke-width: .5px;
stroke-opacity: .5;
}
.land {
fill: #222;
}
.boundary {
fill: none;
stroke: #fff;
stroke-width: .5px;
}
</style>
<body>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//d3js.org/d3.geo.projection.v0.min.js"></script>
<script src="//d3js.org/topojson.v1.min.js"></script>
<script>
var width = 960,
height = 580;
var color = d3.scale.category10();
var range = [0,1,2];
var projection = d3.geo.kavrayskiy7()
.scale(170)
.translate([width / 2, height / 2])
.precision(.1);
var path = d3.geo.path()
.projection(projection);
var graticule = d3.geo.graticule();
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
svg.append("defs").append("path")
.datum({type: "Sphere"})
.attr("id", "sphere")
.attr("d", path);
svg.append("use")
.attr("class", "stroke")
.attr("xlink:href", "#sphere");
svg.append("use")
.attr("class", "fill")
.attr("xlink:href", "#sphere");
svg.append("path")
.datum(graticule)
.attr("class", "graticule")
.attr("d", path);
d3.json("world-50m.json", function(error, world) {
if (error) throw error;
var countries = topojson.feature(world, world.objects.countries).features,
neighbors = topojson.neighbors(world.objects.countries.geometries);
svg.selectAll(".country")
.data(countries)
.enter().insert("path", ".graticule")
.attr("class", "country")
.attr("d", path)
.style("fill", function(d, i) {
// get colors of the already coloured neighbors
var colors = neighbors[i]
.map( function(n){return countries[n].color;})
.filter(function(n){return n != undefined;});
// if none, give the region a random color
if(colors.length==0){
d.color = Math.floor(Math.random() * range.length);
} else {
// otherwise, what are the color remaining?
var remaining_colors = range.filter(function(n) {
return !colors.includes(n);
});
// if there's no remaining color, we push one
if(remaining_colors.length==0){
var new_color = range.length;
d.color = new_color;
range.push(new_color);
console.log('New color: '+color(new_color));
} else {
// otherwise, pick a random color among them
var random_index = Math.floor(
Math.random() * remaining_colors.length
);
d.color = remaining_colors[random_index];
}
}
return color(d.color);
});
svg.insert("path", ".graticule")
.datum(topojson.mesh(world, world.objects.countries, function(a, b) { return a !== b; }))
.attr("class", "boundary")
.attr("d", path);
});
d3.select(self.frameElement).style("height", height + "px");
</script>
Display the source blob
Display the rendered blob
Raw
world-50m.json
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment