D3js: placement automatique des étiquettes pour éviter les chevauchements? (force de répulsion)

à mon avis, la disposition de la force ne convient pas pour placer des étiquettes sur une carte. La raison en est simple: les étiquettes doivent être aussi proches que possible des endroits où elles sont apposées, mais la disposition de la force n'a rien pour l'imposer. En effet, pour la simulation, il n'y a pas de mal à mélanger les étiquettes, ce qui n'est clairement pas souhaitable pour une carte.

il pourrait y avoir quelque chose de mis en œuvre en plus de la disposition de la force qui a les lieux eux-mêmes comme les noeuds fixes et les forces attractives entre le lieu et son étiquette, tandis que les forces entre les étiquettes seraient répulsives. Cela nécessiterait probablement une modification de la disposition de la force (ou plusieurs dispositions de la force en même temps), donc je ne vais pas suivre cette voie.

ma solution repose simplement sur la détection des collisions: pour chaque paire d'étiquettes, vérifiez si elles se chevauchent. Si c'est le cas, déplacez - les hors du chemin, où la direction et l'ampleur du mouvement est dérivée du chevauchement. De cette façon, seules les étiquettes qui se chevauchent réellement sont déplacées, et les étiquettes ne bougent qu'un petit peu. Ce processus est répété jusqu'à ce qu'aucun mouvement ne se produise.

le code est quelque peu alambiqué car la vérification du chevauchement est assez confuse. Je ne vais pas poster tout le code ici, il se trouve dans cette démo (notez que j'ai fait les étiquettes beaucoup plus grandes pour exagérer l'effet). Les clés ressemblent à ceci:

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

le tout est loin d'être parfait -- notez que certaines étiquettes sont assez éloignées de l'endroit où elles sont étiquetées, mais la méthode est universelle et devrait au moins éviter le chevauchement des étiquettes.

L'une des options est d'utiliser la disposition de la force avec des foci multiples . Chaque foyer doit être situé dans le centroïde de la caractéristique, et l'étiquette doit être attirée uniquement par les foyers correspondants. De cette façon, chaque étiquette aura tendance à être près du centroïde de la caractéristique, mais la répulsion avec d'autres étiquettes peut éviter la question de chevauchement.

pour comparaison:

• tutoriel de M. Bostock " faisons une carte" ( carte ),
• mon gist pour un Automatique des Étiquettes de Placement version (carte) mise en oeuvre des foyers de la stratégie.

code correspondant:

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

While ShareMap-dymo.js peuvent travailler, il ne semble pas être très bien documenté. J'ai trouvé une bibliothèque qui fonctionne pour le cas plus général, est bien documenté et utilise également le recuit simulé: D3-Étiqueteuse

j'ai rassemblé un échantillon d'utilisation avec ce jsfiddle .La page d'échantillon D3-Labeler utilise 1000 itérations. J'ai trouvé que c'est plutôt inutile et que 50 itérations semble fonctionner assez bien c'est très rapide, même pour quelques centaines de points de données. Je crois qu'il y a place à amélioration tant dans la façon dont cette bibliothèque s'intègre à D3 qu'en termes d'efficacité, mais je n'aurais pas pu aller aussi loin tout seul. Je vais mettre à jour ce fil si je trouve le temps de soumettre un PR.

voici le code correspondant (voir le lien D3-Labeler pour plus de documentation):

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

pour un examen plus approfondi du fonctionnement de D3-Labeler, voir "Un plug-in D3 pour le placement automatique des étiquettes à l'aide d'une simulation recuit "

Jeff Heaton "Intelligence Artificielle de l'Homme, Volume 1" a également fait un excellent travail à l'explication du processus de recuit simulé.

vous pourriez être intéressé par le composant d3fc-label-layout (pour D3v5) qui est conçu exactement à cet effet. Le composant fournit un mécanisme pour disposer les composants enfants basé sur leurs boîtes rectangulaires. Vous pouvez appliquer une stratégie de recuit avide ou simulée afin de minimiser les chevauchements.

voici un extrait de code qui montre comment appliquer ce composant de layout à L'exemple de carte de 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);

Et voici une petite capture d'écran du résultat:

Vous pouvez voir un exemple complet ici:

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

Divulgation: tel Que discuté dans les commentaires ci dessous, je suis un collaborateur principal de ce projet, si clairement Je suis quelque peu partial. Tout le crédit aux autres réponses à cette question qui nous a donné l'inspiration!

pour l'affaire 2D voici quelques exemples qui font quelque chose de très similaire:

one http://bl.ocks.org/1691430

deux http://bl.ocks.org/1377729

merci Alexander Skaburskis qui a soulevé ce haut ici

pour le cas 1D Pour ceux qui cherchent une solution à un problème similaire en 1-D je peux partager mon sandbox JSfiddle où j'essaie de le résoudre. C'est loin d'être parfait, mais il sorte de faire la chose.

à gauche: le modèle de bac à sable, à droite: un exemple d'utilisation

Voici l'extrait de code que vous pouvez exécuter en appuyant sur le bouton à la fin du post, et aussi le code lui-même. Lors de l'exécution, cliquez sur le champ pour positionner les noeuds fixés.

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>

une option est d'utiliser un agencement Voronoi pour calculer où il y a de l'espace entre les points. Il y a un bon exemple de Mike Bostock ici .

ShareMap-dymo.js est un port de Dymo.py bibliothèque Python créée par Mike Migurski pour JavaScript / ActionScript 3.

La bibliothèque est destinée à être praticable dans 4 environnements:

• Navigateur côté client
• Node.côté serveur js
• Flash/AIR côté client / mobile
• Java de l'environnement, utilisation de Nashorn dans Java 8 et de Rhino dans les versions Java plus anciennes.

en ce moment, les meilleurs environnements d'essai sont les deux premiers, mais les deux derniers sont également développés et benchmark sera publié bientôt.

dans les plans ultérieurs, cette bibliothèque pourra être parfaitement intégrée avec D3 et tract.