Algoritmo de colocación de etiquetas de gráfico de burbujas? (preferiblemente en JavaScript)
Me gustaría colocar automáticamente 100-200 etiquetas de burbujas para que se cumplan los siguientes requisitos:
- Las etiquetas no deben superponerse
- Las etiquetas preferiblemente no deben superponerse a las burbujas
- La etiqueta debe estar cerca de la burbuja
- Posición preferida de la etiqueta (arriba a la izquierda, arriba, abajo, derecha, etc.) debe respetarse en cierta medida
- El tamaño de la fuente puede variar
¿Existen bibliotecas / algoritmos útiles para esto? (preferiblemente JavaScript o PHP)
(La colocación de la etiqueta en la imagen no cumple con estos requisitos)
9 answers
Esto se puede formular como un problema de Programación Lineal. Desea maximizar o minimizar una función (que representa el "peso" o la "bondad" de la solución) sujeta a ciertas restricciones (sus requisitos). Tendrá que formalizar sus requisitos como valores. Algo como esto:
Variables:
x1 = 1 if Labels overlap, 0 otherwise
x2 = some measure of "how much" a label overlaps a bubble
x3 = distance from label to bubble //Label should be close to bubble
x4 = distance between ideal and actual label position
x5 = difference between actual and ideal font size
minimize x1 + 10*x2 + x3 + 20*x4 + 5*x5
subject to constraints:
x1 = 0 // labels can never overlap
x2 < /* maximum amount a label is allowed to overlap a bubble */
...
x5 < 6 // font size does not vary by more than +/- 6 pts.
Hice los coeficientes y las restricciones, puede usarlos para ajustar el resultado en función de qué características son más importantes para usted. Los coeficientes aumentan el valor de un requisito (en este caso, f4 se pondera más por lo que 'más importante'. Las restricciones son límites duros que no pueden ser violados.
Dado que este es un problema bien conocido, ahora puede resolverlo utilizando una serie de métodos. El algoritmo Simplex es popular. Hay un capítulo entero en Cormen et. al acerca de estos problemas.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-02 17:54:20
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-29 22:48:28
Imagino que estás trabajando con javascript, html y css? Bueno, en cualquier caso dos enfoques vienen a la mente.
Primero es formularlo como un problema de optimización. Es necesario calcular la posición ideal para cada etiqueta. Esto se basará en el tamaño de la burbuja, la ubicación deseada (es decir, arriba, abajo, izquierda, derecha) y el tamaño de la etiqueta (tanto la fuente como la longitud). Luego necesita parametrizar sus coordenadas, por ejemplo, en una lista de elementos 2N donde N es el número de etiqueta. Luego debe inicializar las etiquetas en alguna posición (o una población si usa un algoritmo genético) y aplicar un algoritmo de optimización que requerirá una función de costo. Esto se basaría en qué tan lejos está un conjunto de posiciones de etiquetas del ideal, así como cualquier cosa que viole sus reglas, como la superposición.
O, que sea un problema de física. 'Adjuntar' cada etiqueta a su burbuja con algún enlace rígido. Dar a cada etiqueta y cada burbuja una fuerza repelente y también añadir un fuerza graviacional global y más fuerte (en la dirección preferida arriba/izquierda/derecha/abajo). Tenga una simulación física corta hasta que alcance un equilibrio. Las matemáticas no deberían ser muy difíciles.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-06 00:22:30
Creo que si está utilizando D3 dentro de sus herramientas, puede usar el algoritmo de colocación de etiquetas "basado en la fuerza". La solución originalmente pertenece a Max Planck Research Networks pero ya hay un ejemplo de Javascript listo, aquí: Colocación de etiquetas basada en la fuerza en D3
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-08-05 15:56:58
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-06 20:18:06
Desafortunadamente, creo que va a ser difícil encontrar esta solución fácilmente disponible en Javascript o PHP. Pero, creo que su problema se puede dividir en pequeños subproblemas (basados en sus reglas) para ayudarlo a diseñar su solución.
Me gustaría identificar cuáles de sus reglas son las más importantes. Por el aspecto del gráfico que proporcionaste, diría que la regla #1 y #2 proporcionaría la mayor mejora en legibilidad.
Para determinar la colocación de acuerdo con esas reglas, Calcularía los contenedores de límites del texto y las burbujas y probaría la intersección. En la intersección, muévase a una ubicación sin intersección. Si no se puede encontrar uno, utilice un espacio con una superposición mínima.
Esto le permitiría también crear una heurística de colocación ponderada para arriba-izquierda, abajo-derecha, etc., para ayudar a colocar las etiquetas en ubicaciones "preferidas".
Intentaría escribir una pequeña parte del algoritmo de colocación usando dos burbujas con dos etiquetas que son por lo general se cierran y podrían superponerse. Si puede generalizar su algoritmo de colocación para trabajar para este pequeño subconjunto, debería estar bien avanzando con más burbujas.
También, tal vez podría usar algo en el orden de un árbol kd u otra estructura de datos de partición de espacio para localizar vecinos más cercanos a evitar.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-05-02 16:54:29
Encontré un enfoque en Java para este problema que realmente funciona y se llama Force Directed Map Labeling y es una experiencia de open-source academy.
Aquí está la documentación+ código fuente del proyecto: Forzar el Etiquetado de Mapas dirigido
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-12-11 16:50:25
¿Qué tal
Etiqueta.substring (0, Math.sqrt (bubbleValueOrRadius))
Encontré esto en uno de protovis.js examples.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-08-04 01:32:01
Este hilo es muy bueno para cubrir algunos enfoques. Estoy usando el diseño de fuerza con múltiples focos, ya que parece el mejor método general.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:17:06