Estrategia para conectar 2 puntos sin intersectar segmentos de curvas dibujados previamente

9

Tengo que conectar pares de puntos sin intersección. Digamos que tengo dos puntos dados que conecto con un segmento de una curva. Por otra parte, se seleccionan dos nuevos puntos finales y estos nuevos puntos también deben conectarse, sin cruzarse con las curvas dibujadas previamente, y así sucesivamente para cualquier número de pares de puntos dados.

¿Cuál es la forma más fácil de encontrar y dibujar estos segmentos de curvas?

algorithm usuario36552
fuente
¿Líneas o segmentos de línea?
Mokosha
Solo es importante que los dos nuevos puntos estén conectados, por lo tanto, los segmentos de curvas también están bien. Pregunta editada.
user36552
2
Puede buscar algoritmos de búsqueda de ruta para esto. Use segmentos existentes como obstáculos y encuentre un camino entre los dos puntos finales nuevos. Tal vez aplique un poco de suavizado a la ruta resultante para que sea una curva más bonita.
Nathan Reed

Respuestas:

6

El problema general se llama dibujo gráfico y no es un problema fácil.

Las gráficas que se pueden dibujar en el plano sin cruces se llaman planas , pero no todas las gráficas son planas: las gráficas típicas que no son planas son la gráfica completa en vértices y la gráfica bipartita completa en 6 vértices , famoso por el problema de las tres utilidades .5 5K5 5K3,3

Es posible que desee probar Graphviz - Software de visualización de gráficos para producir bonitos dibujos.

Ver también

Szirmay-Kalos, László, Algoritmo de diseño dinámico para mostrar gráficos generales , en Graphics Gems IV , 1994. código

Rosati, Claudio, Un algoritmo de conexión simple para dibujo 2-d, Graphics Gems III , 1992, código .

lhf
fuente
Otras herramientas incluyen yEd (uso gratuito pero sin licencia gratuita), gephi ... este es un problema NP Hard.
joojaa