Algorithmus gesucht: Objekte durch gerades Liniensegment verbinden
-
Hallo,
ich suche ein Stichwort für einen Algorithmus, ihr kennt das bestimmt aus Visio:
Zwei Objekte mit definierten Verankerungsstellen werden durch eine Linie verbunden. Nun handelt es sich aber nicht um eine direkte Linie sondern um ein Liniensegment aus geraden Linien.Das Ganze soll auch dann funktionieren, wenn bspw. ein drittes Element quasi als Hinderniss zwischen die anderen beiden geschoben wird.
Gibt es da einen Standardalgorithmus?
Gruß
Depp.
-
Hast du noch Nebenbedingungen (möglichst kurze Strecke, möglichst wenige Knicke oder Ähnliches) oder reicht irgendeine Verbindung?
-
Hilft dir der A*-Algorithmus (http://de.wikipedia.org/wiki/A*-Algorithmus)?
-
Hallo,
möglichst wenige Knicke wären nicht schlecht, ist jetzt aber auch nicht wirklich zwingend. Ich möchte, dass die Verbindungslinien in ein Ablaufdiagramm integriert werden. Prio-1-Anforderung für mich ist damit, dass das Ganze übersichtlich bleibt.
Gruß
Depp.
-
lol-depp schrieb:
Prio-1-Anforderung für mich ist damit, dass das Ganze übersichtlich bleibt.
"Übersichtlich" ist eine schwer greifbare Anforderung an einen Algorithmus
-
pumuckl schrieb:
lol-depp schrieb:
Prio-1-Anforderung für mich ist damit, dass das Ganze übersichtlich bleibt.
"Übersichtlich" ist eine schwer greifbare Anforderung an einen Algorithmus
Klingt als sollte der mittlere (quadratische?) Abstand zu den Hindernissen möglichst groß werden, wobei aber ein Cutoff eingeführt wird. Zusätzlich definiert man noch zwei Gütefunktionen für Wegstrecke und Knickzahl und verwurstet die drei Werte mittels durch Ausprobieren zu findender Vorfaktoren zu einer Gesamtgüte.
Die Frage ist bloß, wie man dann noch einen Algorithmus finden möchte, der nicht Ausprobieren aller Pfade ist. Ich würde da ein MC-Verfahren probieren, da ja sicherlich nicht unbedingt das perfekt globale Minimum gesucht ist, sondern nur etwas, das nahe dran kommt. Das bräuchte dann ein paar clevere Moves: Aufbrachen einer Strecke in zwei Unterstrecken, Zusammenlegung zweier Unterstrecken und Bewegen der Verbindungspunkte sind noch gut machbar. Aber man bräuchte noch etwas, um auch mal in eine ganz andere Konfiguration zu kommen. Vielleicht parallel gleich mehrere Pfade mit unterschiedlichen Startrichtungen testen. Und an jedem Liniensegment wieder splitten.
Ja, ich kann sehen, dass das funktionieren würde. Da man nicht auf physikalische Ensemblekorrektheit achten braucht, dürfte das sogar gar nicht mal so schwer sein.
