Hallo.
ich habe jetzt Zeit und kann etwas mehr erklären.
Danke.
Zum einen ist es nicht möglich "schräge" Linien zu benutzen, also immer nur senkrechte oder waagrechte Linien (Wendewinkel von 45°).
Das ist eine neue Info, ändert aber so gut wie nichts an der richtigen Herangehensweise.
Das hab ich mittlerweile mir auch überlegt.
und ich glaube du wollstest Wendewinkel 90° sagen.
Ups.
Nehme deinen Startpunkt, Endpunkt und die Eckpunkte aller Hindernisse und werfe sie in einen Topf. Bilde daraus alle möglichen Punktepaare und ziehe für jedes Paar die Verbindungslinie ein, aber NUR wenn die Verbindungslinie kein Hindernis kreuzt (Berührung ist natürlich OK). Das ist dein Sichtbarkeitsgraph.
Das habe ich gemerkt, als ich mir den Dijkstra (es könnte ja auch einfach Meier oder Müller heißen) Algorithmus angeguckt hatte. Dort stand: "Hier ist ein Graph mit allen Verbindungen und den Kosten einer Verbindung bekannt. Ebenfalls ist bekannt, welche Verbindungen von welchem Knoten ausgehen, und zu welchem sie führen." Aber dass das Sichtbarkeitsgraph heißt habe ich nicht gewusst.
Berechnen kannst du das Ding mit einen naiven Ansatz im Grunde genau wie eben beschrieben. Bild zunächst jede erdenkliche Verbindungslinie. Nehme eine Verbindungslinie und teste sie mit allen Hinderniskanten auf Schnitt. Wenn es einen Schnitt gibt, schmeiss die Verbindungslinie weg. Nimm die nächste Verbindungslinie usw. Es gibt zwar Methoden, die den Sicht.Graph. viel schneller berechnen, aber ich glaube du willst lieber fertig werden anstatt algorithmische Geometrie zu studieren.
Hehe, algorithmische Geometrie studieren will ich sicher nicht, aber ich fürchte mit den Methoden mit denen man den Sicht.G. schneller berechnen kann, sollte ich mich auseinandersetzen. Angenommen ich habe 50 Hindernisse (durchaus realistisch), so habe ich dadurch alleine 200 Knoten. Mögliche Knotenverbindungen habe ich dann (nach der Formel meines Mathelehrers n+n/2*(n-3) ) ca. 20'000. Nun muss jede Verbindung an 50 Hindernissen überprüft werden. Macht 1'000'000 Überprüfungen. Mit PHP! Das ist mir zu viel.
Wenn dein Sicht.Graph. steht, dann nimm den Startpunkt und lass damit den Dijkstra Algorithmus laufen. Es wurde dir auch schon ein passender Link gepostet: http://de.wikipedia.org/wiki/Dijkstras_Algorithmus. Der berechnet dir den kürzesten Weg durch den Sichtbarkeitsgraphen und das ist dann auch der kürzeste Weg, den du suchst.
Die Funktionsweise des Dijkstra-Algorithmus hab ich schon verstanden ;)
Nun musst du noch die Verbindungslinien, aus denen sich deine kürzeste Strecke zusammensetzt, durch senkrechte und waagerechte Linien ersetzen.
So hab ich mir das auch schon überlegt.
Gruß
Jasmin/Hartmud