Strategia łączenia 2 punktów bez przecinania wcześniej narysowanych segmentów krzywych

9

Muszę połączyć pary punktów bez przecięcia. Powiedzmy, że mam dwa podane punkty, które łączę z odcinkiem krzywej. Następnie ponownie wybierane są dwa nowe punkty końcowe i te nowe punkty muszą być również połączone, jednak bez przecinania wcześniej narysowanych krzywych itd. Dla dowolnej liczby podanych par punktów.

Jak najłatwiej znaleźć i narysować te segmenty krzywych?

algorithm użytkownik36552
źródło
Linie czy segmenty linii?
Mokosha
Ważne jest tylko, że dwa nowe punkty są połączone, dlatego segmenty krzywych również są OK. Pytanie edytowane.
user36552,
2
Możesz zajrzeć do tego w algorytmach wyszukiwania ścieżek. Użyj istniejących segmentów jako przeszkód i znajdź ścieżkę między dwoma nowymi punktami końcowymi. Być może zastosuj wygładzenie do uzyskanej ścieżki, aby uzyskać ładniejszą krzywą.
Nathan Reed

Odpowiedzi:

6

Ogólny problem nazywa się rysowaniem wykresów i nie jest łatwym problemem.

Wykresy, które można narysować na płaszczyźnie bez skrzyżowań, są nazywane płaskimi , ale nie wszystkie wykresy są płaskie: typowe wykresy, które nie są płaskie, to pełny wykres na wierzchołkach i pełny wykres dwudzielny na 6 wierzchołkach , znany ze względu na problem trzech narzędzi .5K.5K.3),3)

Możesz wypróbować Graphviz - oprogramowanie do wizualizacji wykresów, aby stworzyć ładne rysunki.

Zobacz też

Szirmay-Kalos, László, Algorytm dynamicznego układu do wyświetlania ogólnych wykresów , w Graphics Gems IV , 1994. kod

Rosati, Claudio, Prosty algorytm połączenia do rysowania 2D , Graphics Gems III , 1992, kod .

lhf
źródło
Inne narzędzia to YEd (darmowy, ale bez darmowych wszy), gephi ... jest to trudny problem NP.
joojaa