¿Algoritmo de colocación de etiquetas de burbujas? (Preferiblemente en JavaScript)

Question

me gustaría para colocar automáticamente 100-200 etiquetas de burbujas de modo que se cumplan los siguientes requisitos:

• etiquetas deben no solaparse
• etiquetas preferiblemente no deben superponerse burbujas
• Label debe estar cerca de la burbuja
• posición de la etiqueta preferido (parte superior izquierda, superior, inferior, derecho etc.) deben ser respetados en cierta medida
• Font-tamaño 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)

Answer 1

Esto se puede formular 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á 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 limitaciones, se les puede utilizar para afinar el resultado basan en 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 es "más importante". Las restricciones son límites estrictos que no se pueden violar.

Dado que este es un problema bien conocido, ahora puedes resolverlo usando varios métodos. El algoritmo Simplex es popular. Hay un capítulo completo en Cormen et. al acerca de estos problemas.

Answer 2

¿Qué tal esto?

An Efficient Algorithm for Scatter Chart Labeling

Answer 3

Por desgracia, creo que va a ser difícil de encontrar esta solución fácilmente disponible en Javascript o PHP. Pero, creo que su problema se puede dividir en pequeños sub-problemas (según sus reglas) para ayudarlo a diseñar su solución.

Identificaría cuáles de sus 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, calculo los contenedores de límites del texto y las burbujas y pruebo 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 colocación ponderada para arriba a la izquierda, abajo a la derecha, etc., para ayudar a colocar las etiquetas en ubicaciones "preferidas".

Intentaré escribir una pequeña parte del algoritmo de ubicación utilizando dos burbujas con dos etiquetas que generalmente están cerca y podrían superponerse. Si puede generalizar su algoritmo de ubicación para trabajar en este pequeño subconjunto, debería avanzar moviendo más burbujas.

Además, tal vez podría utilizar algo del orden de un árbol kd u otra estructura de datos de división de espacio para localizar vecinos más cercanos para evitar.

Answer 4

Imagino que está trabajando con javascript, html y css? Bueno, en cualquier caso, vienen a la mente dos enfoques.

Lo 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 (tanto fuente como longitud). Luego necesita 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 usa un algoritmo genético) y aplicar un algoritmo de optimización que requerirá una función de costo. Esto se basaría en cuán lejos están del ideal un conjunto de posiciones de etiqueta, así como cualquier cosa que viole sus reglas, como la superposición.

O, que sea un problema de física. 'Adjunte' cada etiqueta a su burbuja con algún enlace rígido. Dele a cada etiqueta y cada burbuja una fuerza repelente y también agregue una fuerza de gravedad global y más fuerte (en la dirección preferida arriba/izquierda/derecha/abajo). Haga una simulación física corta hasta que llegue a un equilibrio. Las matemáticas no deberían ser demasiado difíciles.

Answer 5

juegan Tal vez con algunos kits de herramientas de ayuda como el siguiente:

• protovis
• d3

Answer 6

¿Qué tal

label.substring (0, Math.sqrt (bubbleValueOrRadius))

I fou Encuentra esto en uno de los ejemplos de protovis.js.

Answer 7

Creo que si usa D3 dentro de sus herramientas, puede usar el algoritmo de colocación de etiquetas "basado en la fuerza". La solución pertenece originalmente a Max Planck Research Networks pero ya existe un ejemplo de JavaScript listo, aquí: Force-based label placement in D3

Answer 8

En realidad, encontré un enfoque en Java para este problema que realmente funciona y se llama Etiquetado de mapa dirigido por la fuerza y ​​es de código abierto experiencia academica

Aquí es el código de la documentación + proyecto de código: Force Directed Map Labeling

Answer 9

This thread es muy bueno en la cobertura de algunos enfoques. Estoy usando el diseño de fuerza con múltiples focos, ya que parece ser el mejor método general.