D3js: Automatic labels placement to avoid overlaps? (force repulsion)

Question

How to apply force repulsion on map's labels so they find their right places automatically ?

---

Bostock' "Let's Make a Map"

Mike Bostock's Let's Make a Map (screenshot below). By default, labels are put at the point's coordinates and polygons/multipolygons's path.centroid(d) + a simple left or right align, so they frequently enter in conflict.

Handmade label placements

One improvement I met requires to add an human made IF fixes, and to add as many as needed, such :

.attr("dy", function(d){ if(d.properties.name==="Berlin") {return ".9em"} }) 

The whole become increasingly dirty as the number of labels to reajust increase :

//places's labels: point objects svg.selectAll(".place-label")     .data(topojson.object(de, de.objects.places).geometries)   .enter().append("text")     .attr("class", "place-label")     .attr("transform", function(d) { return "translate(" + projection(d.coordinates) + ")"; })     .attr("dy", ".35em")     .text(function(d) { if (d.properties.name!=="Berlin"&&d.properties.name!=="Bremen"){return d.properties.name;} })     .attr("x", function(d) { return d.coordinates[0] > -1 ? 6 : -6; })     .style("text-anchor", function(d) { return d.coordinates[0] > -1 ? "start" : "end"; });  //districts's labels: polygons objects. svg.selectAll(".subunit-label")     .data(topojson.object(de, de.objects.subunits).geometries)   .enter().append("text")     .attr("class", function(d) { return "subunit-label " + d.properties.name; })     .attr("transform", function(d) { return "translate(" + path.centroid(d) + ")"; })     .attr("dy", function(d){     //handmade IF         if( d.properties.name==="Sachsen"||d.properties.name==="Thüringen"|| d.properties.name==="Sachsen-Anhalt"||d.properties.name==="Rheinland-Pfalz")             {return ".9em"}         else if(d.properties.name==="Brandenburg"||d.properties.name==="Hamburg")             {return "1.5em"}         else if(d.properties.name==="Berlin"||d.properties.name==="Bremen")             {return "-1em"}else{return ".35em"}}     )     .text(function(d) { return d.properties.name; }); 

Need for better solution

That's just not manageable for larger maps and sets of labels. How to add force repulsions to these both classes: .place-label and .subunit-label?

This issue is quite a brain storming as I haven't deadline on this, but I'am quite curious about it. I was thinking about this question as a basic D3js implementation of Migurski/Dymo.py. Dymo.py's README.md documentation set a large set of objectives, from which to select the core needs and functions (20% of the work, 80% of the result).

1. Initial placement: Bostock give a good start with left/right positionning relative to the geopoint.
2. Inter-labels repulsion: different approach are possible, Lars & Navarrc proposed one each,
3. Labels annihilation: A label annihilation function when one label's overall repulsion is too intense, since squeezed between other labels, with the priority of annihilation being either random or based on a population data value, which we can get via NaturalEarth's .shp file.
4. [Luxury] Label-to-dots repulsion: with fixed dots and mobile labels. But this is rather a luxury.

I ignore if label repulsion will work across layers and classes of labels. But getting countries labels and cities labels not overlapping may be a luxury as well.

Answer 1

In my opinion, the force layout is unsuitable for the purpose of placing labels on a map. The reason is simple -- labels should be as close as possible to the places they label, but the force layout has nothing to enforce this. Indeed, as far as the simulation is concerned, there is no harm in mixing up labels, which is clearly not desirable for a map.

There could be something implemented on top of the force layout that has the places themselves as fixed nodes and attractive forces between the place and its label, while the forces between labels would be repulsive. This would likely require a modified force layout implementation (or several force layouts at the same time), so I'm not going to go down that route.

My solution relies simply on collision detection: for each pair of labels, check if they overlap. If this is the case, move them out of the way, where the direction and magnitude of the movement is derived from the overlap. This way, only labels that actually overlap are moved at all, and labels only move a little bit. This process is iterated until no movement occurs.

The code is somewhat convoluted because checking for overlap is quite messy. I won't post the entire code here, it can be found in this demo (note that I've made the labels much larger to exaggerate the effect). The key bits look like this:

function arrangeLabels() {   var move = 1;   while(move > 0) {     move = 0;     svg.selectAll(".place-label")        .each(function() {          var that = this,              a = this.getBoundingClientRect();          svg.selectAll(".place-label")             .each(function() {               if(this != that) {                 var b = this.getBoundingClientRect();                 if(overlap) {                   // determine amount of movement, move labels                 }               }             });        });   } } 

The whole thing is far from perfect -- note that some labels are quite far away from the place they label, but the method is universal and should at least avoid overlap of labels.

Answer 2

One option is to use the force layout with multiple foci. Each foci must be located in the feature's centroid, set up the label to be attracted only by the corresponding foci. This way, each label will tend to be near of the feature's centroid, but the repulsion with other labels may avoid the overlapping issue.

For comparison:

• M. Bostock's "Lets Make a Map" tutorial (resulting map),
• my gist for an Automatic Labels Placement version (resulting map) implementing the foci's strategy.

The relevant code:

// Place and label location var foci = [],     labels = [];  // Store the projected coordinates of the places for the foci and the labels places.features.forEach(function(d, i) {     var c = projection(d.geometry.coordinates);     foci.push({x: c[0], y: c[1]});     labels.push({x: c[0], y: c[1], label: d.properties.name}) });  // Create the force layout with a slightly weak charge var force = d3.layout.force()     .nodes(labels)     .charge(-20)     .gravity(0)     .size([width, height]);  // Append the place labels, setting their initial positions to // the feature's centroid var placeLabels = svg.selectAll('.place-label')     .data(labels)     .enter()     .append('text')     .attr('class', 'place-label')     .attr('x', function(d) { return d.x; })     .attr('y', function(d) { return d.y; })     .attr('text-anchor', 'middle')     .text(function(d) { return d.label; });  force.on("tick", function(e) {     var k = .1 * e.alpha;     labels.forEach(function(o, j) {         // The change in the position is proportional to the distance         // between the label and the corresponding place (foci)         o.y += (foci[j].y - o.y) * k;         o.x += (foci[j].x - o.x) * k;     });      // Update the position of the text element     svg.selectAll("text.place-label")         .attr("x", function(d) { return d.x; })         .attr("y", function(d) { return d.y; }); });  force.start();