Jasmin: Von A nach B im Koordinatensystem vorbei an Hindernissen

Beitrag lesen

Hallo Jasmin (bleiben wir doch dabei),

Hallo Cruz.

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.

Wahrscheinlich nur mit dir nicht geläufigen Formlen

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

Ja genau, wenn man nur noch um die n^2-n eine Klammer macht (wie sich das gehört ;)) dann ist das genau das gleiche wie n+n/2*(n-3). Zugegeben etwas vereinfacht.

und sie alle mit n Kanten aus der Szene auf Schnitt testen. Insgesamt ergibt das also n^3-n^2 / 2 Schnitttests.

Das ist die Formel von oben mit n multipliziert, was ja auch logisch ist. Ich hatte statt Kanten mit Hindernissen multipliziert, deswegen kam bei mir ja auch nur 1/4 von deinem Ergebnis heraus. Das habe ich deshalb gemacht, weil ich schon vor langer Zeit eine Funktion im Hindernisobjekt geschrieben habe, die prüft, ob das übergebene Objekt im Hinderniss liegt. Dazu muss natürlich auch wieder jede Kante geprüft werden. Insofern hast du recht. Allerdings sind bei mir (vl. kann man das noch verbessern) zur Überprüfung von jeder Kante weitere vier Bedingungen nötig (größer/kleiner). Insgesamt also 16 Vergleiche von x/y Koordinaten pro Hinderniss.

Man nennt das übrigens in der O-Notation O(n^3).

Gut das hilft mir das zu verstehen.

Viele Grüße
Deine Jasmin ;)