Strategie zum Verbinden von 2 Punkten, ohne zuvor gezeichnete Kurvensegmente zu schneiden

9

Ich muss Punktpaare ohne Schnittpunkt verbinden. Angenommen, ich habe zwei vorgegebene Punkte, die ich mit einem Kurvensegment verbinde. Dann werden wieder zwei neue Endpunkte ausgewählt und diese neuen Punkte müssen ebenfalls verbunden werden, jedoch ohne zuvor gezeichnete Kurven usw. für eine beliebige Anzahl gegebener Punktpaare zu schneiden.

Was ist der einfachste Weg, diese Kurvensegmente zu finden und zu zeichnen?

algorithm user36552
quelle
Linien oder Liniensegmente?
Mokosha
Es ist nur wichtig, dass die beiden neuen Punkte verbunden sind, daher sind auch Kurvensegmente in Ordnung. Frage bearbeitet.
user36552
2
Möglicherweise untersuchen Sie hierfür Algorithmen zur Pfadfindung. Verwenden Sie vorhandene Segmente als Hindernisse und suchen Sie einen Pfad zwischen den beiden neuen Endpunkten. Wenden Sie möglicherweise eine Glättung auf den resultierenden Pfad an, um eine schönere Kurve zu erhalten.
Nathan Reed

Antworten:

6

Das allgemeine Problem wird als Diagrammzeichnung bezeichnet und ist kein einfaches Problem.

Die Graphen, die in der Ebene ohne Kreuzungen gezeichnet werden können, werden als planar bezeichnet , aber nicht alle Graphen sind planar: Die typischen Graphen, die nicht planar sind, sind der vollständige Graph auf Eckpunkten und der komplette zweigeteilte Graph auf 6 Eckpunkten , berühmt wegen des Drei-Dienstprogramme-Problems .K 5 K 3 , 35K5K3,3

Vielleicht möchten Sie Graphviz - Graph Visualization Software ausprobieren , um schöne Zeichnungen zu erstellen.

Siehe auch

Szirmay-Kalos, László, Dynamischer Layoutalgorithmus zur Anzeige allgemeiner Grafiken in Graphics Gems IV , 1994. Code

Rosati, Claudio, Ein einfacher Verbindungsalgorithmus für das 2D-Zeichnen, Graphics Gems III , 1992, Code .

lhf
quelle
Andere Tools sind yEd (kostenlos zu verwenden, aber keine kostenlose Lizenz), gephi ... dies ist ein NP Hard-Problem.
Joojaa