Label collision avoidance using D3.js (and Mapbox)

What I have

I have a mapbox map, where a add some Feature points, with a text label showing the name of the location.

I’m trying to add collision detection/avoidance to this so that no labels are colliding. I actually have this working (see picture below), but I wan’t to improve it further.

Currently I’m doing a collision detection using a D3 quadtree, and if two bounding boxes are overlapping (let’s call them A and B), I first check if the have the biggest overlap in the X or the Y direction, and then move them apart from each other in the shortest overlapping direction.

enter image description here

What I need help with

If you look at the map, you can see that some labels are moved quite far away from the corresponding icon (green dot, fixed at original location). For instance the highlighted label “Dublin”. How can I improve the algorithm so it also takes into account the distance to the icon position? “Dublin” could be much closer to the icon on the left side.

What am I looking for?

I don’t necessarily need full code of the solution, just some pointers. I’ve spent too much time thinking about this, so I need some new input.

Implementation

D3.js simulation is just defined like this:

 getSimulation() {
    return (
      d3
        /** Setup a physics based simulation */
        .forceSimulation<Node>()
        .force('collision', this.forceCollide())
        .stop()
    )
  }

The collision detection is defined like this:

/** Collision detection with quadtree.
 *
 * Will compare node to other nodes, using a quadtree,
 * and move them apart of the overlap. If biggest overlap
 * is in x direction, move apart in y direction, or visa versa.
 */
forceCollide() {
  let nodes: Array<Node>

  function force(alpha: number) {
    // for (var i = 0; i < 10; i++) {
    const quadtree = d3
      .quadtree<Node>()
      .x(d => d.x)
      .y(d => d.y)
      .addAll(nodes)
    for (const node of nodes) {
      const l1 = node.x
      const r1 = node.x + node.size[0]
      const t1 = node.y
      const b1 = node.y + node.size[1]

      /**
       * visit each squares in the quadtree x1 y1 x2 y2
       * constitutes the coordinates of the square want
       * to check if each square is a leaf node (has data prop)
       */
      quadtree.visit((visited, x1, y1, x2, y2) => {
        /** Is a leaf node, and is not checking against itself */
        if (isLeafNode(visited) && visited.data.id !== node.id) {
          const l2 = visited.data.x
          const r2 = visited.data.x + visited.data.size[0]
          const t2 = visited.data.y
          const b2 = visited.data.y + node.size[1]

          /** We have a collision */
          if (l2 < r1 && l1 < r2 && t1 < b2 && t2 < b1) {
            /** Calculate intersecting rectangle */
            const xLeft = Math.max(l1, l2)
            const yTop = Math.max(t1, t2)
            const xRight = Math.min(r1, r2)
            const yBottom = Math.min(b1, b2)

            /** Move the rectangles apart, so that they don't overlap anymore. ๐Ÿ™…๐Ÿผ */


            /* Find which direction has biggest overlap */
            if (xRight - xLeft > yBottom - yTop) {
              /** Biggest in x direction (move y) */
              const dy = (yBottom - yTop) / 2
              node.y -= dy
              visited.data.y += dy
            } else {
              /** Biggest in y direction (move x) */
              const dx = (xRight - xLeft) / 2
              node.x -= dx
              visited.data.x += dx
            }
          }
        }
        return x1 > r1 || x2 < l1 || y1 > b1 || y2 < t1
      })
    }
  }

  force.initialize = (_: any) => (nodes = _)

  return force
}

Minimal working example can be found here.

Answer

I’ve ended up making several changes to your code, which I think should improve this behaviour.

  1. (In preparation) I’ve changed the Node.size property from an array to an object:
export interface NodeSize {
  width: number;
  height: number;
}

interface Node {
  ...
  size: NodeSize;
}
  1. Your boxes for the labels were way too big, so they ended up triggering collisions where there were none. I’ve replaced it with a more fine-grained method of finding the text width on a canvas:
/**
 * Measure the width of a text were it to be rendered using a given font.
 *
 * @param {string} text the text to be measured
 * @param {string} font a valid css font value
 *
 * @returns {number} the width of the rendered text in pixels.
 */
function getTextSize(text: string, font = "14px "Open Sans Semibold""): NodeSize {
  const element = document.createElement("canvas");
  const context = element.getContext("2d") as CanvasRenderingContext2D;
  context.font = font;

  const textSize = context.measureText(text);
  return {
    width: textSize.width,
    height: textSize.actualBoundingBoxAscent + textSize.actualBoundingBoxDescent,
  };
}
  1. In order to pull the nodes towards their original positions, I’ve added forceX and forceY to the simulation:
d3.forceSimulation
  .force("collision", rectCollide())
  .force("x", d3.forceX<Node>().x(d => d.lng))
  .force("y", d3.forceY<Node>().y(d => d.lat))
  1. If you only move in the direction of the biggest overlap, then you can eventually get into the positions where nodes are pushing each other vertically, while there is a lot of space horizontally. To reduce the chances of this happening, I propose moving in both directions, by taking the intersecting rectangle you’ve computed, and moving both nodes by it’s width / 2 and height / 2 such that only their corners should touch. This will give the x and y forces more freedom to then pull the nodes then further back to their anchors:
type TNodeBounds = {
  t: number,
  r: number,
  b: number,
  l: number
}

function getOffsets(node1: TNodeBounds, node2: TNodeBounds): { dx: number, dy: number } {
  /** Calculate intersecting rectangle */
  const xLeft = Math.max(node1.l, node2.l);
  const yTop = Math.max(node1.t, node2.t);
  const xRight = Math.min(node1.r, node2.r);
  const yBottom = Math.min(node1.b, node2.b);
  const xCenter = (xLeft + xRight) / 2;
  const yCenter = (yTop + yBottom) / 2;

  let dx = 0, dy = 0;
  if((node1.l <= node2.l && node1.r >= node2.r)
      || (node2.l <= node1.l && node2.r >= node1.r)) {
    // The larger node completely spans the smaller node, don't move sideways, since it won't matter
  } else if(node1.l <= node2.l) {
    // Node 1 is left of node 2
    dx = xCenter - xLeft;
  } else {
    // Node 1 is right of node 2
    dx = -(xCenter - xLeft);
  }

  if((node1.t <= node2.t && node1.b >= node2.b)
      || (node2.t <= node1.t && node2.b >= node1.b)) {
    // The taller node completely spans the smaller node, don't move up/down, since it won't matter
  } else if(node1.t <= node2.t) {
    // Node 1 is above node 2
    dy = yCenter - yTop;
  } else {
    // Node 1 is below node 2
    dy = -(yCenter - yTop);
  }
  return { dx, dy };
}
/** Move the rectangles apart, so that they don't overlap anymore. ๐Ÿ™…๐Ÿผ */
const { dx, dy } = getOffsets(
    { l: l1, t: t1, r: r1, b: b1 },
    { l: l2, t: t2, r: r2, b: b2 }
);
node.x -= dx;
visited.x += dx;

node.y -= dy;
visited.y += dy;