Cruz: Von A nach B im Koordinatensystem vorbei an Hindernissen

Beitrag lesen

Hallo Jasmin wäre mir lieber gewesen :),

ich habe jetzt Zeit und kann etwas mehr erklären.

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. Du arbeitest also in der sogenannten "Manhatten-Metrik" http://de.wikipedia.org/wiki/Manhattan-Metrik, und ich glaube du wollstest Wendewinkel 90° sagen.

Trotzdem brauchst du erstmal den Sichtbarkeitsgraphen. Was ist das? 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. Man kann sich auch anschaulich vorstellen, dass es genau dann eine Verbindungslinie zwischen zwei Eckpunkten gibt, wenn die Ecken sich gegenseitig "sehen" können und kein Hindernis die Sicht blockiert. 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.

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.

Nun musst du noch die Verbindungslinien, aus denen sich deine kürzeste Strecke zusammensetzt, durch senkrechte und waagerechte Linien ersetzen.

Gruß
Cruz