Cruz: Von A nach B im Koordinatensystem vorbei an Hindernissen

Beitrag lesen

Hallo Jasmin (bleiben wir doch dabei),

Das habe ich gemerkt, als ich mir den Dijkstra (es könnte ja auch einfach Meier oder Müller heißen) Algorithmus angeguckt hatte. [...] Aber dass das Sichtbarkeitsgraph heißt habe ich nicht gewusst.

Das ist so nicht ganz korrekt. Der Dijkstra Algorithmus arbeitet allgemein auf einen Graphen mit gewichteten Kanten. Der Sichtbarkeitsgraph ist nur ein spezieller Graph, der in der Geometrie verwendet wird. Die Knoten sind die Eckpunkte der Hindernisse, die Kanten die kürzesten Wege zwischen den Eckpunkten und die Kantengewichte sind dann einfach die Längen der Kanten, also die Distanz zwischen zwei Eckpunkten. Also der Dijkstra arbeitet nicht grundsätzlich auf Sicht.G., sondern der Sicht.G. ist ein Graph, auf den man den Dijkstra anwenden kann.

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.

Ähm...die Rechnung ist etwas schräg. Sagen wir du hast in deiner Szene n Knoten. Dann hast du ebenfalls n Kanten (die Seiten der Hindernisse). Für den Sicht.G. musst du genau n^2-n / 2 Verbindungen in Betracht ziehen und sie alle mit n Kanten aus der Szene auf Schnitt testen. Insgesamt ergibt das also n^3-n^2 / 2 Schnitttests.
Das wären bei 200 Knoten also ziemlich genau 3.980.000 Tests.
Man nennt das übrigens in der O-Notation O(n^3).

Mit einem noch relativ verständlichen radialen Sweep kann man den Sicht.G. in O(n^2 log n) berechnen. Mit einem getunten aber kaum noch verständlichen simultanen Sweep geht es sogar in O(n^2). Mehr ist leider nicht drin, also richtig schnell wird es nie.

Aber:
200^3 = 8.000.000
200^2 * log(200) = 320.000 (ca.)
200^2 = 40.000

das macht schon einen fetten Unterschied.

Gruß
Cruz