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

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,

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

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 . $5$ $K_5$ $K_{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