使用 D3.js（和 Mapbox）避免标签碰撞

Question

我有什么

我有一个 mapbox 地图，其中添加了一些特征点，并带有显示位置名称的文本标签。

我正在尝试为此添加碰撞 detection/avoidance，这样标签就不会发生碰撞。我实际上有这个工作（见下图），但我不想进一步改进它。

目前我正在使用 D3 四叉树进行碰撞检测，如果两个边界框重叠（我们称它们为 A 和 B），我首先检查是否有最大的边界框在X或Y方向重叠，然后在最短重叠方向上将它们分开。

我需要什么帮助

如果你看一下地图，你会发现一些标签被移到了离相应图标很远的地方（绿点，固定在原来的位置）。例如突出显示的标签“都柏林”。 我如何改进算法，使其也考虑到图标位置的距离？“都柏林”可以更靠近左侧的图标。

我在寻找什么？

我不一定需要解决方案的完整代码，只需要一些提示。我花了太多时间思考这个问题，所以我需要一些新的意见。

实施

D3.js模拟就是这样定义的：

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

碰撞检测是这样定义的：

/** 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 1

我最终对您的代码做了几处更改，我认为这应该会改善这种行为。

（准备中）我已经将 Node.size 属性从数组更改为对象：

export interface NodeSize {
  width: number;
  height: number;
}

interface Node {
  ...
  size: NodeSize;
}

你的标签框太大了，所以它们最终在 none 的地方触发了碰撞。我已将其替换为 a more fine-grained method 在 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,
  };
}

为了将节点拉向它们的原始位置，我在模拟中添加了 forceX 和 forceY：

d3.forceSimulation
  .force("collision", rectCollide())
  .force("x", d3.forceX<Node>().x(d => d.lng))
  .force("y", d3.forceY<Node>().y(d => d.lat))

如果你只朝重叠最大的方向移动，那么你最终可以进入节点在垂直方向相互推动的位置，而水平方向有很多 space。为了减少发生这种情况的可能性，我建议在两个方向上移动，通过采用您计算出的相交矩形，并将两个节点移动 width / 2 和 height / 2 这样只有它们的角应该接触。这会给 x 和 y 力量更多的自由，然后将节点拉回它们的锚点：

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;

使用 D3.js（和 Mapbox）避免标签碰撞

Label collision avoidance using D3.js (and Mapbox)

javascript

collision-detection

quadtree

d3.js

mapbox-gl-js

我有什么

我需要什么帮助

我在寻找什么？

实施