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.

Inkerman

I think that adding force repulsion to the place labels can make some labels go off their respective region. Other thing to consider is that different kind of labels can overlap in some maps, the name of a city can be over the name of the country, with very distint fonts though. I think that the definitive solution may be more complex that just add repulsion. – Freewheeling

I've used a force layout to position labels here: larsko.org/v/igdp/index-alt.html Your case is more complex as it involves two dimensions, but you might be able to reuse some of the code. – Marque

@PabloNavarro: First, how to apply repulsion on my items. Later on, the force can be subtile. It need a repulsion quickly decreasing with distance, kind of R = 1/x. This adjustment will be an other issue. – Inkerman

I implemented a demo of the aforementioned strategy. It's not perfect, but it can help. bl.ocks.org/pnavarrc/5913636 – Freewheeling

I know that this is not force-repulsion related, but as Mike Bostock pointed out in the tutorial, there's this script github.com/migurski/Dymo that should do the trick (I wasn't able to make it work tho, I even posted a question here to get some advice but hey hopefully you can!) – Cede

While powerful, Dymo.py is a Python approach which is quite counter productive within D3js / clientside web-cartography ecosystem. I'am rather opening a long term talk for a pure D3js approach, likely more basic, yet efficient and sufficient. – Inkerman

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.

Marque

Oh and the whole thing can of course be implemented much more efficiently! – Marque

In my anwser, I propose a the labels to be attracted to the places, but repelled between them. However, the force layout doesn´t guarantee that the labels won´t overlap. The method proposed here could work, but it doesn´t guarantee that the labels will be near the original place. I think that a combination of force layout, text-alignment and small adjustements could work in most cases, but again, without guarantees. – Freewheeling

Yes, this is not a problem with a straightforward solution. Dymo looks like the best solution, but obviously porting that to Javascript would be quite a bit of work. – Marque

I was thinking about a basic D3js version of Dymo.py, with core functions, doing 80% of the work. I clarified the question about requirements, since this question is more a long term brain storming for a challenging D3js / web-cartography issue. – Inkerman

Sidenote: I +1ed this answer, but someone else -1-ed it. I guess it's not Pablo, since he knows how hard this question is. But if someone pass by, please +1 Lars answer and Navarrc answer, as they are both witty answers to a tricky issue. – Inkerman

@Pablo-navarro / Lars: I have to grant the bounty to someone in a fair way, what do you thing ? – Inkerman

Well my solution certainly doesn't achieve everything you ask for (I think that's a project too big for an SO question). I'll leave the decision up to you -- fine either way really. – Marque

A performance improvement, if needed for large numbers of items, is to sort on the x and y axis. Then you can easily focus on candidates for overlap and ignore everything out of range. So on X, an object starting at 2 and 5 wide can only overlap with the ones sorted after it that start between 2 and 7. The sort is cheaper than the compare everything with everything. – Decongestant

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();

Freewheeling

Your code works. On the other hand, I hadn't time to test further with different forces or to develop other ways. I validated your answer for now but I may eventually validate a better answer if one arise. This issue is central to map making, I hope an awesome solution will emerge in the coming months. – Inkerman

I think that a force that vanishes more quickly with the distance can lead to a better layout. – Freewheeling

Update: Some versions ago, the force layout allows to set a maximum distance of action, which will improve this method a bit (you can see the labels on the northest regions being repelled by all the labels). The updated gist bl.ocks.org/pnavarrc/5913636 – Freewheeling

@PabloNavarro's suggestion is the best overall choice. Lars's choice will put labels random places so long as they don't overlap. This provides ordering. – Eveliaevelin

I think this is the best solution. I use it on my current project and it was fast and quite easy. One thing I changed: to prevent labels from moving, I run the force layout a fixed number of times, and then display labels as in Mike Bostock example bl.ocks.org/mbostock/1667139 . – Moult

That’s a great suggestion @etiennecrb, though I would iterate until force.alpha() < 1e-2, which in general happens in under 20-30 iterations (depending on the network structure). – Freewheeling

Answer 3

While ShareMap-dymo.js may work, it does not appear to be very well documented. I have found a library that works for the more general case, is well documented and also uses simulated annealing: D3-Labeler

I've put together a usage sample with this jsfiddle.The D3-Labeler sample page uses 1,000 iterations. I have found this is rather unnecessary and that 50 iterations seems to work quite well - this is very fast even for a few hundred data points. I believe there is room for improvement both in the way this library integrates with D3 and in terms of efficiency, but I wouldn't have been able to get this far on my own. I'll update this thread should I find the time to submit a PR.

Here is the relevant code (see the D3-Labeler link for further documentation):

var label_array = [];
var anchor_array = [];

//Create circles
svg.selectAll("circle")
.data(dataset)
.enter()
.append("circle")
.attr("id", function(d){
    var text = getRandomStr();
    var id = "point-" + text;
    var point = { x: xScale(d[0]), y: yScale(d[1]) }
    var onFocus = function(){
        d3.select("#" + id)
            .attr("stroke", "blue")
            .attr("stroke-width", "2");
    };
    var onFocusLost = function(){
        d3.select("#" + id)
            .attr("stroke", "none")
            .attr("stroke-width", "0");
    };
    label_array.push({x: point.x, y: point.y, name: text, width: 0.0, height: 0.0, onFocus: onFocus, onFocusLost: onFocusLost});
    anchor_array.push({x: point.x, y: point.y, r: rScale(d[1])});
    return id;                                   
})
.attr("fill", "green")
.attr("cx", function(d) {
    return xScale(d[0]);
})
.attr("cy", function(d) {
    return yScale(d[1]);
})
.attr("r", function(d) {
    return rScale(d[1]);
});

//Create labels
var labels = svg.selectAll("text")
.data(label_array)
.enter()
.append("text")
.attr("class", "label")
.text(function(d) {
    return d.name;
})
.attr("x", function(d) {
    return d.x;
})
.attr("y", function(d) {
    return d.y;
})
.attr("font-family", "sans-serif")
.attr("font-size", "11px")
.attr("fill", "black")
.on("mouseover", function(d){
    d3.select(this).attr("fill","blue");
    d.onFocus();
})
.on("mouseout", function(d){
    d3.select(this).attr("fill","black");
    d.onFocusLost();
});

var links = svg.selectAll(".link")
.data(label_array)
.enter()
.append("line")
.attr("class", "link")
.attr("x1", function(d) { return (d.x); })
.attr("y1", function(d) { return (d.y); })
.attr("x2", function(d) { return (d.x); })
.attr("y2", function(d) { return (d.y); })
.attr("stroke-width", 0.6)
.attr("stroke", "gray");

var index = 0;
labels.each(function() {
    label_array[index].width = this.getBBox().width;
    label_array[index].height = this.getBBox().height;
    index += 1;
});

d3.labeler()
    .label(label_array)
    .anchor(anchor_array)
    .width(w)
    .height(h)
    .start(50);

labels
    .transition()
    .duration(800)
    .attr("x", function(d) { return (d.x); })
    .attr("y", function(d) { return (d.y); });

links
    .transition()
    .duration(800)
    .attr("x2",function(d) { return (d.x); })
    .attr("y2",function(d) { return (d.y); });

For a more in depth look at how D3-Labeler works, see "A D3 plug-in for automatic label placement using simulated annealing"

Jeff Heaton's "Artificial Intelligence for Humans, Volume 1" also does an excellent job at explaining the simulated annealing process.

Prospect

also for a force directed approach I was able to put this fiddle together jsfiddle.net/s3logic/j789j3xt which I derived from: bl.ocks.org/ilyabo/2585241 ... but I couldn't get it to work so well outside of the Dorling cartogram application – Prospect

This is really the best solution. Label placement must be done through constrained optimization and no "force layout" can get similar results. We've used it in our project and it works ok – Quincuncial

This works fairly well. The only issue is it runs the algorithm on points that do not need to move. – Eveliaevelin

Answer 4

You might be interested in the d3fc-label-layout component (for D3v5) that is designed exactly for this purpose. The component provides a mechanism for arranging child components based on their rectangular bounding boxes. You can apply either a greedy or simulated annealing strategy in order to minimise overlaps.

Here's a code snippet which demonstrates how to apply this layout component to Mike Bostock's map example:

const labelPadding = 2;

// the component used to render each label
const textLabel = layoutTextLabel()
  .padding(labelPadding)
  .value(d => d.properties.name);

// a strategy that combines simulated annealing with removal
// of overlapping labels
const strategy = layoutRemoveOverlaps(layoutGreedy());

// create the layout that positions the labels
const labels = layoutLabel(strategy)
    .size((d, i, g) => {
        // measure the label and add the required padding
        const textSize = g[i].getElementsByTagName('text')[0].getBBox();
        return [textSize.width + labelPadding * 2, textSize.height + labelPadding * 2];
    })
    .position(d => projection(d.geometry.coordinates))
    .component(textLabel);

// render!
svg.datum(places.features)
     .call(labels);

And this is a small screenshot of the result:

You can see a complete example here:

http://bl.ocks.org/ColinEberhardt/389c76c6a544af9f0cab

Disclosure: As discussed in the comment below, I am a core contributor of this project, so clearly I am somewhat biased. Full credit to the other answers to this question which gave us inspiration!

Procurator

Thanks for mentioning the component. I've always missed a thorough implementation solving this problem. You should, however, add a disclosure, that it is your own project. – Miner

@Miner - good call, I've added a disclosure that indicates my bias towards this solution. Thanks! – Procurator

Hello @ColinE, thanks you. The disclosure is cool : cool to see some people getting inspired by SO than contributing back, by answers and by code. Great :) – Inkerman

@Procurator Hi, thanks for the lib. But how can I use it with another lib like mapbox or leaflet.js ? It there a way to pass to fc.layoutLabel(strategy) some array with x,y,width,height and get an array of new arranged coordinates? Thanks – Clyster

@Procurator Is there a way to build the textLabels with more than just text? I'd like to have some <tspan> elements to style things. – Procession

Answer 5

For 2D case here are some examples that do something very similar:

one http://bl.ocks.org/1691430
two http://bl.ocks.org/1377729

thanks Alexander Skaburskis who brought this up here

---

For 1D case For those who search a solution to a similar problem in 1-D i can share my sandbox JSfiddle where i try to solve it. It's far from perfect but it kind of doing the thing.

Left: The sandbox model, Right: an example usage

Here is the code snippet which you can run by pressing the button in the end of the post, and also the code itself. When running, click on the field to position the fixed nodes.

var width = 700,
    height = 500;

var mouse = [0,0];

var force = d3.layout.force()
    .size([width*2, height])
    .gravity(0.05)
    .chargeDistance(30)
    .friction(0.2)
    .charge(function(d){return d.fixed?0:-1000})
    .linkDistance(5)
    .on("tick", tick);

var drag = force.drag()
    .on("dragstart", dragstart);

var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height)
    .on("click", function(){
        mouse = d3.mouse(d3.select(this).node()).map(function(d) {
            return parseInt(d);
        });
        graph.links.forEach(function(d,i){
            var rn = Math.random()*200 - 100;
            d.source.fixed = true; 
            d.source.px = mouse[0];
            d.source.py = mouse[1] + rn;
            d.target.y = mouse[1] + rn;
        })
        force.resume();
        
        d3.selectAll("circle").classed("fixed", function(d){ return d.fixed});
    });

var link = svg.selectAll(".link"),
    node = svg.selectAll(".node");
 
var graph = {
  "nodes": [
    {"x": 469, "y": 410},
    {"x": 493, "y": 364},
    {"x": 442, "y": 365},
    {"x": 467, "y": 314},
    {"x": 477, "y": 248},
    {"x": 425, "y": 207},
    {"x": 402, "y": 155},
    {"x": 369, "y": 196},
    {"x": 350, "y": 148},
    {"x": 539, "y": 222},
    {"x": 594, "y": 235},
    {"x": 582, "y": 185}
  ],
  "links": [
    {"source":  0, "target":  1},
    {"source":  2, "target":  3},
    {"source":  4, "target":  5},
    {"source":  6, "target":  7},
    {"source":  8, "target":  9},
    {"source":  10, "target":  11}
  ]
}

function tick() {
  graph.nodes.forEach(function (d) {
     if(d.fixed) return;
     if(d.x<mouse[0]) d.x = mouse[0]
     if(d.x>mouse[0]+50) d.x--
    })
    
    
  link.attr("x1", function(d) { return d.source.x; })
      .attr("y1", function(d) { return d.source.y; })
      .attr("x2", function(d) { return d.target.x; })
      .attr("y2", function(d) { return d.target.y; });

  node.attr("cx", function(d) { return d.x; })
      .attr("cy", function(d) { return d.y; });
}

function dblclick(d) {
  d3.select(this).classed("fixed", d.fixed = false);
}

function dragstart(d) {
  d3.select(this).classed("fixed", d.fixed = true);
}



  force
      .nodes(graph.nodes)
      .links(graph.links)
      .start();

  link = link.data(graph.links)
    .enter().append("line")
      .attr("class", "link");

  node = node.data(graph.nodes)
    .enter().append("circle")
      .attr("class", "node")
      .attr("r", 10)
      .on("dblclick", dblclick)
      .call(drag);

.link {
  stroke: #ccc;
  stroke-width: 1.5px;
}

.node {
  cursor: move;
  fill: #ccc;
  stroke: #000;
  stroke-width: 1.5px;
  opacity: 0.5;
}

.node.fixed {
  fill: #f00;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.4.11/d3.min.js"></script>
<body></body>

Heliogabalus