D3js：如何自动放置标签以避免重叠？（力斥原理）

Question

D3js：如何自动放置标签以避免重叠？（力斥原理）

d3.jsmapsforce-layouttopojsoncartography

59

如何在地图的标签上应用力的排斥作用，以使它们能够自动地找到正确的位置？

Bostock的 “让我们创建一张地图”

迈克·博斯托克（Mike Bostock）的让我们创建一张地图（下面是截图）。默认情况下，标签会放置在点的坐标和多边形 / 多重多边形的 path.centroid(d) + 简单的左对齐或右对齐，因此它们经常发生冲突。

enter image description here

手工标签放置

我遇到的一个改进方法需要添加一个人工制作的IF修复程序，并根据需要添加尽可能多的修复程序，例如：

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

随着需要重新调整的标签数量增加，整个情况变得越来越脏。

//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; });

需要更好的解决方案

对于更大的地图和标签集，这是难以管理的。如何为这两个类：.place-label 和 .subunit-label 添加力斥功能？

这个问题相当棘手，因为我没有截止日期，但我非常好奇。我将这个问题视为 Migurski/Dymo.py 的基本 D3js 实现。Dymo.py 的 README.md 文档设置了大量的目标，我们从中选择核心需求和功能（20% 的工作量，80% 的结果）。

初始放置： Bostock 通过相对于地理点的左/右位置给出一个好的开始。
标签间的斥力： 可以采用不同的方法，Lars 和 Navarrc 分别提出了一种方法。
标签消除： 当一个标签的整体斥力太强时，由于被夹在其他标签之间，需要一个标签消除函数，优先级可以是随机的或者基于population数据值，我们可以通过 NaturalEarth 的 .shp 文件获取该值。
[豪华] 标签与点的斥力: 固定的点和移动的标签。但这只是一种奢侈品。

我不知道标签斥力是否适用于跨层和标签类别。但避免国家标签和城市标签重叠可能也是一种奢侈。

- Hugolpz

我认为在地点标签中添加力斥可以使一些标签离开它们各自的区域。另一个需要考虑的问题是，在某些地图上，不同类型的标签可能会重叠，城市的名称可能会覆盖国家的名称，尽管字体非常不同。我认为最终的解决方案可能比仅仅添加斥力更加复杂。 - Pablo Navarro

我在这里使用了力导向布局来定位标签：http://www.larsko.org/v/igdp/index-alt.html。你的情况更加复杂，因为它涉及到两个维度，但你可能可以重用一些代码。 - Lars Kotthoff

@PabloNavarro：首先，如何在我的项目上应用排斥力。随后，力量可以微妙地变化。它需要一种随着距离快速减小的排斥力，类似于R = 1/x。这个调整将是另一个问题。 - Hugolpz

我实现了上述策略的演示。它并不完美，但可以帮助。http://bl.ocks.org/pnavarrc/5913636 - Pablo Navarro

我知道这与力和排斥无关，但正如Mike Bostock在教程中指出的那样，有这个脚本 https://github.com/migurski/Dymo 可以解决问题（尽管我无法使其正常工作，我甚至发布了一个问题来寻求一些建议，但希望你能够做到！） - tomtomtom

尽管Dymo.py很强大，但在D3js / 客户端Web制图生态系统中使用它会相当低效。我更倾向于采用纯D3js方法进行长期探讨，可能更基本，但却高效且足够。 - Hugolpz

5个回答

22

一种选择是使用多个聚焦力的强制布局。每个聚焦点必须位于要素的质心处，设置标签仅被相应的聚焦点所吸引。这样，每个标签都倾向于靠近要素的质心，但与其他标签的排斥可能会避免重叠问题。

作为比较：

M. Bostock的“让我们制作地图”教程（生成的地图）
我的gist用于实现聚焦策略的自动标签放置版本（生成的地图）。

相关代码：

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

enter image description here

- Pablo Navarro

你的代码可行。然而，我没有时间用不同的力量进行进一步测试或开发其他方法。目前我已经验证了你的答案，但如果有更好的答案出现，我可能会最终验证它。这个问题对于地图制作非常重要，我希望在未来几个月里能出现一个很棒的解决方案。 - Hugolpz

1

我认为，随着距离的增加而迅速消失的力量可以导致更好的布局。 - Pablo Navarro

2

更新：几个版本之前，强制布局允许设置最大作用距离，这将稍微改善这种方法（您可以看到最北部地区的标签被所有标签排斥）。更新的要点是http://bl.ocks.org/pnavarrc/5913636/。 - Pablo Navarro

@PabloNavarro的建议是最佳选择。Lars的选择会将标签放置在随机位置，只要它们不重叠。这提供了排序。 - Union find

2

我认为这是最好的解决方案。我在我的当前项目中使用它，速度很快，而且相当容易。我改变了一件事：为了防止标签移动，我运行了固定次数的力导向布局，然后按照Mike Bostock的示例http://bl.ocks.org/mbostock/1667139显示标签。 - etiennecrb

这是一个很好的建议@etiennecrb，不过我会迭代直到force.alpha() < 1e-2，通常在20-30次迭代内完成（取决于网络结构）。 - Pablo Navarro

15

虽然ShareMap-dymo.js可能可以工作，但它似乎没有很好的文档。我找到了一个更适用于一般情况、文档良好并且还使用模拟退火的库：D3-Labeler

我已经使用这个jsfiddle编写了使用示例。D3-Labeler样本页面使用了1000次迭代。我发现这是相当不必要的，50次迭代似乎可以很好地工作 - 即使对于几百个数据点也非常快。我认为在这个库与D3集成的方式和效率方面都有改进的空间，但我无法独自完成到这一步。如果我有时间提交PR，我将更新此线程。

以下是相关代码（有关更多文档，请参见D3-Labeler链接）：

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

要深入了解D3-Labeler的工作原理，请参阅"A D3 plug-in for automatic label placement using simulated annealing"

Jeff Heaton的《人类的人工智能，卷1》也很好地解释了模拟退火过程。

- Jordan

此外，对于力导向方法，我能够组合出这个小工具 http://jsfiddle.net/s3logic/j789j3xt/ ，它是从这里得来的：http://bl.ocks.org/ilyabo/2585241 ... 但是我发现在 Dorling 图上以外的应用中效果不是很好。 - Jordan

3

这确实是最佳方案。标签位置必须通过约束优化来完成，没有“力导向布局”可以获得类似的结果。我们在项目中使用过它，效果还不错。 - Rustam

这个工作相当不错。唯一的问题是它在不需要移动的点上运行算法。 - Union find

11

你可能会对 d3fc-label-layout 组件感兴趣（适用于D3v5），它专门为此目的设计。该组件提供一种机制，根据子组件的矩形边界框进行排列。您可以应用贪婪或模拟退火策略以最小化重叠。

下面是一个代码片段，演示如何将此布局组件应用于Mike Bostock的地图示例：

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

以下是结果的小截图：

您可以在此处查看完整示例：

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

声明：正如下面的评论中所讨论的那样，我是该项目的核心贡献者，因此我有一定的偏见。全功归于其他回答此问题并给予我们灵感的人！

- ColinE

1

感谢提到这个组件。我一直缺乏一个彻底的实现来解决这个问题。但是，您应该添加一个披露，说明这是您自己的项目。 - altocumulus

1

@altocumulus - 好主意，我已经添加了一份声明，表明我对这个解决方案有偏见。谢谢！ - ColinE

1

你好@ColinE，谢谢你。这个揭示很酷：很酷的是看到一些人受SO的启发回馈社区，通过答案和代码做出贡献。太棒了 :) - Hugolpz

2

@ColinE 你好，感谢提供这个库。但是我该如何将它与其他库（如mapbox或leaflet.js）一起使用呢？是否有一种方法可以将包含x、y、width、height的数组传递给fc.layoutLabel(strategy)，并获得一个新排列坐标的数组呢？谢谢。 - SERG

@ColinE 有没有办法在textLabel中构建不仅仅是文本的内容？我想要一些<tspan>元素来进行样式设置。 - Leeroy

3

对于2D情况，这里有一些非常相似的示例：

一个http://bl.ocks.org/1691430
两个http://bl.ocks.org/1377729

感谢Alexander Skaburskis在这里提出了这个问题here

对于1D情况对于那些在1-D中寻找类似问题解决方案的人，我可以分享我的沙盒JSfiddle，我试图解决它。它还不完美，但它基本上做到了。

左：沙盒模型，右：用法示例 enter image description here

这是代码片段，你可以通过按下帖子末尾的按钮来运行它，并且也是代码本身。运行时，请单击字段以定位固定节点。

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>

- Angie

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lars Kotthoff · Accepted Answer

在我看来，力导向布局不适合用于在地图上放置标签的目的。原因很简单——标签应该尽可能靠近它们所表示的位置，但是力导向布局没有任何强制要求这样做。实际上，就模拟而言，混淆标签并没有什么坏处，这显然对地图不利。

可以在力导向布局的基础上实现一些内容，使得其将地点作为固定节点，并在地点和其标签之间产生吸引力，而标签之间的相互作用力则是排斥力。这可能需要修改力导向布局的实现方式（或同时使用几个力导向布局），因此我不会采取这种方法。

我的解决方案简单地依赖于碰撞检测：对于每对标签，检查它们是否重叠。如果是这种情况，将它们移出去，移动的方向和大小由重叠程度决定。这样，只有实际重叠的标签才会被移动，而且标签只会移动一点点。这个过程会迭代进行，直到不再发生移动。

代码有些复杂，因为检查重叠非常混乱。我不会在这里贴出整个代码，可以在此演示中找到它（请注意，我已经将标签放大了很多以夸张效果）。关键部分如下所示：

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

整个方法远非完美--请注意有些标签离它们所标记的位置相当远，但该方法是通用的，至少应该避免标签的重叠。 enter image description here