Algoritmo rápido para el bin de dos dimensiones con una distancia mínima de cada rectángulo y un punto

Lo que tengo es una serie de datos anotados, y cuando dibujo el gráfico, quiero colocar las anotaciones en la posición que en general minimiza la distancia desde el punto anotado.

Este cuadro, (robado gratuitamente) muestra lo que me gustaría hacer: .

Sé que este es un problema de optimización, pero no tengo idea de por dónde empezar. Lo que estaba haciendo primero, fue colocarlo en la x correspondiente, y subir y bajar y para encontrar la ubicación que estaba disponible y guardar el área que se dibujó. Si bien funcionó, realmente no hace el mejor uso del espacio disponible, y me pregunto si hay algo mejor.

Me pregunto si hay algún algoritmo conocido que ataque este o similares problemas.

Nota agregada: No necesita ser óptima, pero absolutamente necesita ser rápida. Esto se hace durante el procesamiento, por lo que la IU está bloqueada mientras se ejecuta.

Fuente

2012-01-19 Reverend Gonzo

Si no necesita ser óptimo (y no ha proporcionado una definición clara de lo que desea optimizar), ¿de qué manera una solución puede ser subóptima para aumentar la velocidad? –

Quiero minimizar la distancia desde el punto anotado. (Cada anotación tiene un (x, y) que anota). –

Si el algoritmo que mencionas (es decir, moviendo hacia arriba/abajo y para encontrar una ubicación que estaba disponible) es demasiado lento, entonces probablemente no hay una solución lo suficientemente buena para ti ! – ElKamina

Hay una amplia gama de enfoques para este problema difícil. Sugeriría comenzar en el artículo de Wikipedia en automatic label placement. También puede obtener algunas ideas del dominio de force-based algorithms for graph drawing.

Fuente

2012-01-19 19:40:32

Impresionante ... este es el tipo de cosas que estaba buscando. –

@ReverendGonzo - ¡Qué bueno que Wikipedia está de vuelta en línea! :) –

Lo haría así: use un algoritmo simple de "primer ajuste" y comience con un orden arbitrario para colocar las etiquetas. Califique el resultado con algo así como la suma de la distancia al cuadrado de cada punto anotado. Haría la distancia al cuadrado para evitar tenerlos a todos muy cerca, excepto por uno que está muy lejos.

Si su primera solución es inferior a cierto umbral, úselo y continúe. Si no es así, realice los ajustes más desfavorables (es decir, las etiquetas que están más alejadas del punto anotado) y muévalos hacia arriba en el orden de colocación y comience nuevamente. Itere esto hasta que obtenga una solución que sea lo suficientemente buena o se quede sin tiempo, en cuyo caso debe tomar la mejor solución del lote e irse con ella.

Fuente

2012-01-19 19:44:50

Algoritmo rápido para el bin de dos dimensiones con una distancia mínima de cada rectángulo y un punto

Respuesta

Cuestiones relacionadas