¿Algoritmo de colocación de etiquetas de burbujas?(preferiblemente en JavaScript)
algorithm visualization (9)
¿Qué tal esto?
Un algoritmo eficiente para el etiquetado del gráfico de dispersión
Me gustaría colocar automáticamente 100-200 etiquetas de burbuja para que se cumplan los siguientes requisitos:
- Las etiquetas no deben superponerse
- Las etiquetas preferiblemente no deben solaparse con burbujas
- La etiqueta debe estar cerca de la burbuja
- La posición preferida de la etiqueta (arriba a la izquierda, arriba, abajo, derecha, etc.) debe respetarse hasta cierto punto
- El tamaño de letra puede variar
¿Hay bibliotecas / algoritmos útiles para esto? (preferiblemente JavaScript o PHP)
(La colocación de la etiqueta en la imagen no cumple con estos requisitos)
Creo que si está utilizando D3 dentro de sus herramientas, puede usar un 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 para usar, aquí: Colocación de etiquetas basada en la fuerza en D3
Desafortunadamente, creo que será difícil encontrar esta solución fácilmente disponible en Javascript o PHP. Pero sí creo que su problema se puede dividir en pequeños subproblemas (según sus reglas) para ayudarlo a diseñar su solución.
Identificaría cuáles de tus reglas son las más importantes. A juzgar por el aspecto del gráfico que proporcionó, diría que las reglas n. ° 1 y n. ° 2 proporcionarían la mayor mejora en la legibilidad.
Para determinar la ubicación de acuerdo con esas reglas, calcularía los contenedores de límites del texto y las burbujas y evaluaría la intersección. En la intersección, muévase a una ubicación sin intersección. Si no se puede encontrar uno, use un espacio con una superposición mínima.
Esto le permitiría también crear una heurística de ubicación ponderada para la parte superior izquierda, inferior derecha, etc., para ayudar a colocar las etiquetas en ubicaciones "preferidas".
Intentaría escribir una pequeña parte del algoritmo de colocación utilizando dos burbujas con dos etiquetas que generalmente están cerca y que posiblemente se superpongan. Si puede generalizar su algoritmo de ubicación para trabajar en este pequeño subconjunto, debería avanzar moviendo más burbujas.
Además, quizás podría usar algo del orden de un kd-tree u otra estructura de datos de partición espacial para ubicar a los vecinos más cercanos para evitarlos.
Encontré un enfoque en Java para este problema que realmente funciona y se llama Etiquetado de Mapa Dirigido por la Fuerza y es una experiencia de academia de código abierto.
Aquí está el código fuente de documentación + proyecto: etiquetado de mapa dirigido por la fuerza
Esto puede formularse como un problema de programación lineal. Desea maximizar o minimizar una función (que representa el "peso" o "bondad" de la solución) sujeto a ciertas restricciones (sus requisitos). Tendrás que formalizar tus requerimientos 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.
Inventé los coeficientes y las restricciones, puede usarlos para ajustar el resultado según las características que sean más importantes para usted. Los coeficientes aumentan el valor de un requisito (en este caso, f4 es la más ponderada, por lo que es ''más importante''. Las restricciones son límites difíciles que no pueden violarse.
Dado que este es un problema bien conocido, ahora puede resolverlo utilizando varios métodos. El algoritmo Simplex es popular. Hay un capítulo completo en Cormen et. Al sobre estos problemas.
Me 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. Necesita 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 (fuente y longitud). Luego debe parametrizar sus coordenadas, por ejemplo, en una lista de elementos 2N donde N es el número de etiquetas. Luego debe inicializar las etiquetas en alguna posición (o una población si utiliza un algoritmo genético) y aplicar un algoritmo de optimización que requerirá una función de costo. Esto se basaría en la distancia a la que se encuentra el conjunto de posiciones de la etiqueta del ideal, así como en cualquier cosa que infrinja sus reglas, como la superposición.
O, haz que sea un problema de física. ''Adjunte'' cada etiqueta a su burbuja con algún enlace rígido. Dale a cada etiqueta y cada burbuja una fuerza de repulsión y también agrega una fuerza de escritura global y más fuerte (en la dirección superior / izquierda / derecha / abajo preferida). Haga una simulación física corta hasta que llegue a un equilibrio. Las matemáticas no deberían ser demasiado difíciles.
Qué tal si
label.substring (0, Math.sqrt (bubbleValueOrRadius))
Encontré esto en uno de los ejemplos de protovis.js.
Este hilo es muy bueno para cubrir algunos enfoques. Estoy utilizando el diseño de fuerza con múltiples focos, ya que parece ser el mejor método general.