D3js: Автоматическое размещение меток во избежание дублирования? (отталкивание силы)

Ответ 1

По моему мнению, компоновка сидений не подходит для размещения меток на карте. Причина проста: ярлыки должны быть как можно ближе к местам, которые они маркируют, но силовой макет не имеет ничего общего с этим. Действительно, что касается моделирования, нет никакого вреда в смешивании меток, что явно нежелательно для карты.

В дополнение к силовому макету может быть что-то реализованое, в котором есть места как фиксированные узлы и силы притяжения между местом и его меткой, в то время как силы между ярлыками будут отталкивать. Для этого, скорее всего, потребуется модифицированная реализация макета (или несколько макетов силы одновременно), поэтому я не собираюсь идти по этому маршруту.

Мое решение опирается просто на обнаружение конфликтов: для каждой пары меток проверяйте, перекрываются ли они. Если это так, переместите их в сторону, где направление и величина движения происходит из перекрытия. Таким образом, только метки, которые фактически перекрываются, перемещаются вообще, а метки только немного перемещаются. Этот процесс повторяется до тех пор, пока не произойдет движение.

Код несколько запутан, потому что проверка на перекрытие довольно беспорядочна. Я не буду публиковать весь код здесь, его можно найти в этой демонстрации (обратите внимание, что я сделал ярлыки намного большими, чтобы преувеличивать эффект). Ключевые биты выглядят так:

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

Все это далеко не идеально - обратите внимание, что некоторые ярлыки находятся довольно далеко от места, которое они обозначают, но этот метод универсален и должен, по крайней мере, избегать перекрытия меток.

Ответ 2

Один из вариантов заключается в использовании схемы force с несколькими фокусами. Каждый фокус должен располагаться в центральном объекте, настраивать ярлык, привлекаемый только соответствующими фокусами. Таким образом, каждая метка будет близка к центроиду функции, но отталкивание с другими ярлыками может избежать проблемы перекрытия.

Для сравнения:

• M. Bostock Учебник "Давайте сделаем карту" (итоговая карта)
• my 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 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();

Ответ 3

В то время как 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, см. " Плагин D3 для автоматического размещения меток с использованием имитируемых отжига "

Джефф Хитон "Искусственный интеллект для людей, том 1" также отлично справляется с объяснением моделируемого процесса отжига.

Ответ 4

Вам может быть интересен компонент d3fc-label-layout (для D3v4), который предназначен именно для этой цели. Компонент обеспечивает механизм организации дочерних компонентов на основе прямоугольных ограничивающих прямоугольников. Вы можете применить либо жадную, либо смоделированную стратегию отжига, чтобы минимизировать перекрытия.

Вот фрагмент кода, который демонстрирует, как применить этот компонент макета к примеру карты Майка Бостока:

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

Раскрытие информации: Как обсуждалось в комментарии ниже, я являюсь основным источником этого проекта, поэтому я явно несколько предвзято. Полный ответ на другой ответ на этот вопрос, который дал нам вдохновение!

Ответ 5

Для двумерного случая вот несколько примеров, которые делают что-то очень похожее:

one http://bl.ocks.org/1691430
два http://bl.ocks.org/1377729

спасибо Александру Скабурскису, который принес это здесь

В случае 1D Для тех, кто ищет решение аналогичной проблемы в 1-D, я могу поделиться своей песочницей JSfiddle, где я пытаюсь ее решить. Это далеко не безупречно, но это как бы то, что нужно делать.

Слева: модель песочницы, справа: пример использования

Вот фрагмент кода, который вы можете запустить, нажав кнопку в конце сообщения, а также сам код. При запуске щелкните по полю, чтобы поместить фиксированные узлы.

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>

Ответ 6

Один из вариантов заключается в использовании компоновки Voronoi для вычисления, где есть место между точками. Вот хороший пример от Майка Бостока здесь.

Ответ 7

ShareMap-dymo.js - это порт Dymo.py Библиотека Python, созданная Майком Мигурским для JavaScript/ActionScript 3.

Библиотека предназначена для запуска в 4 средах:

• Клиентская сторона браузера
• Node.js серверная сторона
• Клиентская сторона Flash/AIR/mobile
• Java-среда, используя Nashorn в Java 8 и Rhino в более старых версиях Java.

В настоящее время лучшая тестовая среда - первая, но две последние также разработаны, и скоро будет опубликован бенчмарк.

В более поздних планах эта библиотека будет интегрирована с D3 и LeafLet с безупречной интеграцией.