D3js：自动标签放置，以避免重叠？ （强制排斥）

如何在地图的标签上应用排斥力，自动find合适的位置？

---

博斯托克“让我们来做一个地图”

迈克·博斯托克的让我们做一个地图 （截图如下）。 默认情况下，标签放在点的坐标和多边形/多边形的path.centroid(d) +一个简单的左或右alignment，所以他们经常input冲突。

手工制作的标签展示位置

我遇到的一个改进就是需要添加一个人工修改的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; }); 

需要更好的解决scheme

这对大型地图和标签集来说是不可pipe理的。 如何给这两个类添加强制排斥： .place-label和.subunit-label ？

这个问题是相当头脑风暴，因为我没有这个最后期限，但我很好奇。 我正在考虑这个问题，作为Migurski / Dymo.py的基本D3js实现。 Dymo.py的README.md文档设定了大量目标，从中select核心需求和function（20％的工作，80％的结果）。

1. 初始位置：博斯托克相对于地理位置的左/右定位有一个好的开始。
2. 标签间排斥：不同的方法是可能的，Lars＆Navarrc各提出一个，
3. 标签湮灭：一个标签的总体排斥力太强烈，因为其他标签之间有挤压，湮没的优先级是随机的或基于population数据值，我们可以通过NaturalEarth的.shp文件得到的标签湮灭函数。
4. [豪华] 标签到点的排斥：固定点和移动标签。 但这相当奢侈。

我忽略了标签排斥是否会跨越层和类别的标签。 但让国家标签和城市标签不重叠也可能是一种奢侈。

Answer 1

在我看来，强制布局不适合在地图上放置标签的目的。 原因很简单 – 标签应该尽可能贴近他们标签的位置，但是力量布局没有任何实施。 事实上，就仿真而言，混合标签没有什么坏处，这对于地图来说显然是不可取的。

在布局之上可能会有一些东西，这些东西本身就是地点和标签之间的固定节点和吸引力，而标签之间的力量是相互排斥的。 这可能需要一个修改的力布局实现（或同时的几个部队布局），所以我不会沿着这条路线走。

我的解决scheme只依赖于碰撞检测：对于每一对标签，检查它们是否重叠。 如果是这样的话，把它们移开，其中运动的方向和大小来自重叠。 这样，只有实际重叠的标签完全移动，标签只移动一点点。 这个过程迭代直到不发生移动。

代码有点令人费解，因为检查重叠是相当混乱的。 我不会在这里发布整个代码，它可以在这个演示中find（请注意，我已经使标签大得多以夸大效果）。 关键位是这样的：

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

整个事情远非完美 – 请注意，有些标签离他们标签的位置相当远，但是这个方法是通用的，至less应该避免标签的重叠。

Answer 2

一种select是使用具有多个焦点的力布局 。 每个焦点必须位于特征的中心，设置标签只能被相应的焦点吸引。 这样，每个标签将倾向于靠近该特征的质心，但与其他标签的排斥可避免重叠问题。

为了比较：

• M. Bostock的“让我们制作一个地图”教程 （ 结果地图 ），
• 我的要点是自动标签放置版本（导致地图）执行焦点的战略。

相关代码：

 // 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 dx; }) .attr('y', function(d) { return dy; }) .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) oy += (foci[j].y - oy) * k; ox += (foci[j].x - ox) * k; }); // Update the position of the text element svg.selectAll("text.place-label") .attr("x", function(d) { return dx; }) .attr("y", function(d) { return dy; }); }); force.start(); 

Answer 3

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

我已经把这个jsfiddle的使用示例放在一起。D3 -Labeler示例页面使用了1,000次迭代。 我发现这样做是不必要的，50次迭代似乎工作得很好 – 即使是几百个数据点，速度也非常快。 我相信在这个图书馆与D3集成的方式和效率方面还有改进的空间，但是我不能自己去解决这个问题。 我会更新这个线程，如果我find时间提交公关。

下面是相关的代码（更多文档，请参阅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 dx; }) .attr("y", function(d) { return dy; }) .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 (dx); }) .attr("y1", function(d) { return (dy); }) .attr("x2", function(d) { return (dx); }) .attr("y2", function(d) { return (dy); }) .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 (dx); }) .attr("y", function(d) { return (dy); }); links .transition() .duration(800) .attr("x2",function(d) { return (dx); }) .attr("y2",function(d) { return (dy); }); 

要更深入地了解D3-Labeler的工作原理，请参阅“用于使用模拟退火自动放置标签的D3插件”

Jeff Heaton的“人类人工智能第1卷”在解释模拟退火过程中也做了出色的工作。

Answer 4

您可能对为此devise的d3fc-label-layout组件（D3v4）感兴趣。 该组件提供了一种基于矩形边界框来排列子组件的机制。 您可以应用贪婪或模拟退火策略，以尽量减less重叠。

下面是一个代码片段，演示了如何将这个布局组件应用到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

披露：正如在下面的评论中所讨论的，我是这个项目的核心贡献者，所以我显然有些偏见。 充分相信这个问题的其他答案给了我们灵感！

Answer 5

对于2D案例，这里是一些非常相似的例子：

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

感谢Alexander Skaburskis把这个带到这里

---

对于一维情况对于那些在一维中search类似问题的解决scheme，我可以共享我的沙箱JSfiddle，我试图解决它。 这并不完美，但它是做这件事。

左图：沙盒模型右图：示例用法

这里是代码片段，你可以通过按下在post结尾的button，也是代码本身。 运行时，单击该字段以定位固定节点。

 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(dx<mouse[0]) dx = mouse[0] if(dx>mouse[0]+50) dx-- }) 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 dx; }) .attr("cy", function(d) { return dy; }); } 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="ajax/libs/d3/3.4.11/d3.min.js"></script> <body></body> 

Answer 6

一种select是使用Voronoi布局来计算点之间有空间的地方。 Mike Bostock 在这里有一个很好的例子。

Answer 7

ShareMap-dymo.js是由Mike Migurski为JavaScript / ActionScript 3创build的Dymo.py Python库的一个端口。

该图书馆的目的是在4个环境中运行：

• 浏览器客户端
• Node.js服务器端
• Flash / AIR客户端/移动
• Java环境，在J​​ava 8中使用Nashorn，在较旧的Java版本中使用Rhino。

目前最好的testing环境是前两个testing环境，但是后两个环境也是开发的，基准testing将很快发布。

在后面的计划中，这个库将被启用与D3和LeafLet的完美结合。