d3.js - examples - force directed graph d3

D3js: colocación automática de etiquetas para evitar solapamientos?(fuerza de repulsión)

Question

¿Cómo aplicar la fuerza de repulsión en las etiquetas del mapa para que encuentren sus lugares correctos automáticamente?

Bostock "Hagamos un mapa"

Mike Bostock''s Hagamos un mapa (captura de pantalla a continuación). De forma predeterminada, las etiquetas se colocan en las coordenadas del punto y en la path.centroid(d) polígonos / multipolígonos path.centroid(d) + una alineación simple a la izquierda o a la derecha, por lo que entran frecuentemente en conflicto.

Ubicaciones de etiquetas hechas a mano

Una de las mejoras que encontré requiere agregar correcciones IF hechas por el ser humano y agregar tantas como sea necesario, tales como:

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

El conjunto se vuelve cada vez más sucio a medida que aumenta el número de etiquetas para reajustar:

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

Necesidad de una mejor solución

Eso simplemente no es manejable para mapas más grandes y conjuntos de etiquetas. Cómo agregar las repulsiones de fuerza a estas dos clases: .place-label y .subunit-label ?

Este problema es un gran asalto ya que no tengo fecha límite para esto, pero estoy bastante curioso al respecto. Estaba pensando en esta pregunta como una implementación básica de D3js de Migurski / Dymo.py La documentación README.md de Dymo.py establece un gran conjunto de objetivos, a partir de los cuales se seleccionan las necesidades y funciones principales (20% del trabajo, 80% del resultado).

1. Colocación inicial: Bostock da un buen comienzo con la posición izquierda / derecha relativa al punto geográfico.
2. Repulsión entre etiquetas: diferentes enfoques son posibles, Lars y Navarrc propusieron uno cada uno,
3. Aniquilación de etiquetas: una función de aniquilación de etiqueta cuando la repulsión general de una etiqueta es demasiado intensa, ya que se aprieta entre otras etiquetas, con la prioridad de aniquilación aleatoria o basada en un valor de datos de population , que podemos obtener a través del archivo .shp de NaturalEarth.
4. [Lujo] Repulsión de etiqueta a puntos: con puntos fijos y etiquetas móviles. Pero esto es más bien un lujo.

Ignoro si la repulsión de etiquetas funcionará en capas y clases de etiquetas. Pero conseguir que las etiquetas de los países y las etiquetas de las ciudades no se superpongan también puede ser un lujo.

Answer 1

Aunque ShareMap-dymo.js puede funcionar, no parece estar muy bien documentado. Encontré una biblioteca que funciona para el caso más general, está bien documentada y también utiliza el recocido simulado: D3-Labeler

He creado una muestra de uso con este jsfiddle . La página de muestra D3-Labeler usa 1,000 iteraciones. He descubierto que esto es bastante innecesario y que 50 iteraciones parecen funcionar bastante bien, esto es muy rápido incluso para unos pocos cientos de puntos de datos. Creo que hay margen de mejora tanto en la forma en que esta biblioteca se integra con D3 como en términos de eficiencia, pero no hubiera podido llegar tan lejos por mi cuenta. Actualizaré este hilo si encuentro el momento de enviar un PR.

Aquí está el código relevante (vea el enlace D3-Labeler para más documentación):

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

Para ver más a fondo cómo funciona D3-Labeler, consulte "Un complemento D3 para la colocación automática de etiquetas mediante el recocido simulado"

"Inteligencia Artificial para Humanos, Volumen 1" de Jeff Heaton también hace un excelente trabajo al explicar el proceso de recocido simulado.

Answer 2

En mi opinión, el diseño de fuerza no es adecuado para colocar etiquetas en un mapa. La razón es simple: las etiquetas deben estar lo más cerca posible de los lugares que etiquetan, pero el diseño de la fuerza no tiene nada que hacer cumplir esto. De hecho, en lo que respecta a la simulación, no hay daño al mezclar las etiquetas, lo que claramente no es deseable para un mapa.

Podría haber algo implementado en la parte superior del diseño de la fuerza que tenga los lugares en sí mismos como nodos fijos y fuerzas atractivas entre el lugar y su etiqueta, mientras que las fuerzas entre las etiquetas serían repulsivas. Esto probablemente requiera una implementación de diseño de fuerza modificada (o varios diseños de fuerza al mismo tiempo), así que no voy a seguir esa ruta.

Mi solución se basa simplemente en la detección de colisiones: para cada par de etiquetas, compruebe si se superponen. Si este es el caso, aléjelos del camino, donde la dirección y la magnitud del movimiento se derivan de la superposición. De esta forma, solo se mueven las etiquetas que realmente se superponen, y las etiquetas solo se mueven un poco. Este proceso se itera hasta que no se produce movimiento.

El código es algo intrincado porque verificar la superposición es bastante desordenado. No publicaré todo el código aquí, se puede encontrar en esta demostración (tenga en cuenta que he ampliado las etiquetas para exagerar el efecto). Los bits clave se ven así:

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

Todo está lejos de ser perfecto: tenga en cuenta que algunas etiquetas están bastante alejadas del lugar que etiquetan, pero el método es universal y al menos debe evitar la superposición de etiquetas.

Answer 3

Para el caso 2D aquí hay algunos ejemplos que hacen algo muy similar:

uno http://bl.ocks.org/1691430
dos http://bl.ocks.org/1377729

gracias Alexander Skaburskis que trajo esto here

Para 1D caso Para aquellos que buscan una solución a un problema similar en 1-D puedo compartir mi sandbox JSfiddle donde intento resolverlo. Está lejos de ser perfecto, pero es algo que hace la cosa.

Izquierda: El modelo de la zona de pruebas, Derecha: un ejemplo de uso

Aquí está el fragmento de código que puede ejecutar presionando el botón al final de la publicación, y también el código en sí. Cuando se ejecuta, haga clic en el campo para ubicar los nodos fijos.

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>

Answer 4

Puede que le interese el d3fc-label-layout (para D3v4) que está diseñado exactamente para este propósito. El componente proporciona un mecanismo para organizar los componentes secundarios en función de sus recuadros delimitadores rectangulares. Puede aplicar una estrategia de recocido codiciosa o simulada para minimizar las superposiciones.

Aquí hay un fragmento de código que muestra cómo aplicar este componente de diseño al ejemplo del mapa 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);

Y esta es una pequeña captura de pantalla del resultado:

Puedes ver un ejemplo completo aquí:

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

Divulgación: como se comenta en el comentario a continuación, soy un colaborador central de este proyecto, por lo que estoy un tanto parcializado. ¡Crédito total a las otras respuestas a esta pregunta que nos dieron inspiración!

Answer 5

Una opción es usar el diseño de fuerza con múltiples focos . Cada foco debe estar ubicado en el centroide de la entidad, configurar la etiqueta para que sea atraída solo por los focos correspondientes. De esta forma, cada etiqueta tenderá a estar cerca del centroide de la entidad, pero la repulsión con otras etiquetas puede evitar el problema de superposición.

Para comparacion:

• El tutorial de M. Bostock "Lets Make a Map" ( mapa resultante ),
• mi bl.ocks.org/pnavarrc/5913636 para una versión de Colocación automática de etiquetas (mapa resultante) implementando la estrategia de los focos.

El código relevante:

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

Answer 6

Una opción es usar un diseño de Voronoi para calcular dónde hay espacio entre los puntos. Hay un buen ejemplo de Mike Bostock here .

Answer 7

ShareMap-dymo.js es un puerto de Dymo.py Python library creado por Mike Migurski para JavaScript / ActionScript 3.

La biblioteca está pensada para ser ejecutable en 4 entornos:

• Lado del cliente del navegador
• Lado del servidor Node.js
• Flash / AIR del lado del cliente / móvil
• Entorno Java, utilizando Nashorn en Java 8 y Rhino en versiones anteriores de Java.

En este momento, el mejor entorno de prueba son los primeros dos uno, pero los dos últimos también están desarrollados y el índice de referencia se publicará pronto.

En los planes posteriores, esta biblioteca estará habilitada para integrarse perfectamente con D3 y LeafLet.