c++ - polilineas - no me aparece la distancia en autocad
Segmentos de línea que no se intersecan minimizando la longitud acumulada (4)
Este es el mínimo emparejamiento euclidiano en 2D . El enlace contiene una bibliografía de lo que se sabe sobre este problema. Dado que desea minimizar la longitud total, la restricción de no intersección es redundante, ya que la longitud de cualquier par de segmentos que se crucen puede reducirse al desviarlos.
Me gustaría encontrar un algoritmo mejor para resolver el siguiente problema:
Hay N puntos de inicio (púrpura) y N puntos de destino (verde) en 2D. Quiero un algoritmo que conecte los puntos de inicio con los puntos de destino mediante un segmento de línea (marrón) sin que ninguno de estos segmentos se cruce (rojo) y al mismo tiempo minimice la longitud acumulada de todos los segmentos.
Mi primer esfuerzo en C ++ fue permutar todos los estados posibles, encontrar estados libres de intersecciones y, entre ellos, el estado con la longitud de segmento total mínima O (n!) . Pero creo que tiene que haber una mejor manera.
¿Alguna idea? ¿O buenas palabras clave para buscar?
Parece que se podría usar un algoritmo de BSP-type .
Utilice este algoritmo con orden O (n 3 ) :
El algoritmo húngaro es un algoritmo de optimización combinatoria que resuelve el problema de asignación en tiempo polinomial.
¿Cómo puede ayudar? Bueno, encontrará solo la longitud mínima acumulada. Pero...
CUANDO LA LONGITUD TOTAL ES MÍNIMA, NO HAY INTERSECCIÓN.
Entonces, como @ qq3 dijo que la restricción de intersección es redundante y después de eliminar esta restricción, puede reducir el orden de O (n!) A O (n 3 ) .
Puede seleccionar una conexión aleatoria, luego, cada vez que elimine una cruz (de hecho, cambie la conexión de sus puntos finales), este algoritmo funciona y finaliza en pasos finitos. puede ser que diga que cambiar las causas de cruces a otra, no importa, cada vez que cambie de una cruz, minimizará la longitud total de su respuesta y de esta manera no puede ser infinito (porque la longitud total de las líneas es finita). Realmente funciona en O (F * n ^ 2) donde F= sum of all line segments * power of 10 (para hacerlo entero). Esta O es muy optimista, creo que si prueba este algoritmo simple funcionará bien. Claro que es mucho mejor que la fuerza bruta en general.