Estratégia para conectar 2 pontos sem cruzar segmentos de curvas previamente desenhados

9

Eu tenho que conectar pares de pontos sem interseção. Digamos que eu tenho dois pontos que eu conecto com um segmento de uma curva. Então, novamente, dois novos pontos de extremidade são selecionados e esses novos pontos também precisam ser conectados, sem interceptar curvas desenhadas anteriormente e assim por diante para qualquer número de pares de pontos.

Qual é a maneira mais fácil de encontrar e desenhar esses segmentos de curvas?

algorithm user36552
fonte
Linhas ou segmentos de linha?
Mokosha
É importante apenas que os dois novos pontos estejam conectados; portanto, segmentos de curvas também são bons. Pergunta editada.
user36552
2
Você pode procurar por algoritmos de localização de caminho para isso. Use os segmentos existentes como obstáculos e encontre um caminho entre os dois novos pontos de extremidade. Talvez aplique alguma suavização no caminho resultante para torná-lo uma curva mais agradável.
Re

Respostas:

6

O problema geral é chamado de desenho gráfico e não é um problema fácil.

5K5K3,3

Você pode tentar o Graphviz - Graph Visualization Software para produzir bons desenhos.

Veja também

Szirmay-Kalos, László, Algoritmo de layout dinâmico para exibição de gráficos gerais , em Graphics Gems IV , 1994. código

Rosati, Claudio, Um algoritmo de conexão simples para desenho bidimensional , Graphics Gems III , 1992, código .

lhf
fonte
Outras ferramentas incluem yEd (grátis para usar, mas sem licença grátis), gephi ... esse é um problema do NP Hard.
Joojaa