Jasmin: Von A nach B im Koordinatensystem vorbei an Hindernissen

Beitrag lesen

Hallo.

Trotzdem brauchst du erstmal den Sichtbarkeitsgraphen. Was ist das? Nehme deinen Startpunkt, Endpunkt und die Eckpunkte aller Hindernisse und werfe sie in einen Topf.

Ich habe nun aufgegeben zu verstehen wie man auf eien Sicht.Graph. in der Laufzeit O(n²) kommt. Allerdings habe ich mir etwas selbst überlegt. Mir ist aufgefallen, dass von ca. 50 Hindernissen nur ganz wenige eine Rolle spielen. Deshalb nehme ich am Anfang einfach nur zwei Knoten, den Start- und den Endpunkt. Danach gehe ich wie folgt vor:

Es werden alle Verbindungen untersucht, die die Knoten verbinden (am Anfang nur eine). Liegt eine Verbindung auf einem Hinderniss, wird überprüft, ob das Hinderniss schon mit einbezogen wurde. Wurde es noch nicht, werden die vier Knoten des rechteckigen Hindernisses miteinbezogen und alles geht von neuem los.
Dabei habe ich aber noch eine Frage: Wie berechne ich, ob eine _Strecke_ ein Rechteck schneidet? Das ist viel schwieriger als zwei Rechtecke, das habe ich mittlerweile mit vier Bedingungen geschafft.

Nun hab ich meinen Graph.

Wenn dein Sicht.Graph. steht, dann nimm den Startpunkt und lass damit  den Dijkstra Algorithmus laufen. [...] Der berechnet dir den kürzesten Weg durch den Sichtbarkeitsgraphen und das ist dann auch der kürzeste Weg, den du suchst.

Das ist noch der einfachere Teil.

Grüße Jasmin