nicht angemeldet
Von A nach B im Koordinatensystem vorbei an Hindernissen
Hallo liebe Forumsgemeinde,
ich habe gerade an einem theoretischen Problem zu knabbern.
Ich will in PHP die kürzeste Strecke von einem Punkt A(x/y) zu einem Punkt B(x/y), vorbei an rechteckigen Hindernissen (x1/y1/x2/y2). Meine bisherige Umsetzung macht noch viele Umwege ;)
Ich hab auch schon bei Google gesucht, hab aber glaube ich nicht die richtigen Suchbegriffe gehabt.
Grüße
Jasmin
P.S: Ich weiß nicht, ob "Programmiertechnick" hier der richtige Themenbereich ist, aber ich fand das "PHP" noch weniger passt.
-
Hallo Hartmud/Jasmin,
ich habe gerade an einem theoretischen Problem zu knabbern.
Ich will in PHP die kürzeste Strecke von einem Punkt A(x/y) zu einem Punkt B(x/y), vorbei an rechteckigen Hindernissen (x1/y1/x2/y2). Meine bisherige Umsetzung macht noch viele Umwege ;)
wie sieht diese bisher aus?
P.S: Ich weiß nicht, ob "Programmiertechnick" hier der richtige Themenbereich ist, aber ich fand das "PHP" noch weniger passt.
Du hast ganz sicher den richtigen Themenbereich gewählt, die Problemlösung Deiner Optimierungsaufgabe sollte schließlich in jeder Programmiersprache umsetzbar sein.
Freundliche Grüße
Vinzenz
-
An einem ähnlichem Problem habe ich auch mal gesessen aber nicht umgesetzt. Da ich aber im Studium eine Vorlesung zur Standortplanung gehört habe (Uni Kaiserslautern), weiß ich, dass dort die entsprechenden Probleme behandelt werden.
Versuch es doch mal so: Berechne die Schnittpunkt des direkten Weges mit den Hindernissen, dann hast du ja nur noch zwei Möglichkeiten: links oder rechts rum. Wie weit du exakt gehen musst ist dann natürlich schwierig zu sagen. Vielleicht gibt es auch keine Algorithmus dazu, sondern nur ein Näherungsverfahren.
Versuchs mal hier:
http://optimierung.mathematik.uni-kl.de/e-WiMS/
oder hier
http://i11www.iti.uni-karlsruhe.de/algo/teaching/SS_03/eisenbahn_modelle/
oder hier
http://www.mathematik.uni-kl.de/~lola/docu_prov.html
ingo b
-
Hallo Vinzenz,
wie sieht diese bisher aus?
Ich habe einen sehr ähnlichen Lösungsansatz wie Rabby verfolgt. Da ich nur senkrecht oder waagrechte Linien haben kann, habe ich mir eine Treppenlänge ausgedacht (z.B. 100). So gehe ich immer 100 Punkte waagrecht und dann wieder 100 Punkte senkrecht, bis ich mein Zeil erreicht habe. Wenn Hindernisse in die Quere kommen, gehe ich (je nach Lage des Ziels, Auftreffen auf das Hindernis) am Hindernis vorbei. Dabei ist mir klar geworden, dass der Ansatz, immer nur in Richtung Ziel zu gehen falsch ist. Ein Beispiel: Ober dem Anfangspunkt liegt ein Hindernis. Zuerst gehe ich nach links (da das Ziel weiter links liegt). Dann will ich nach oben gehen, merke das dort das Hindernis ist. Nun muss das Hindernis rechts umlaufen werden. Dadurch ist ein großer Umweg entstanden. Als mir klar wurde, das ich am Anfang nicht das Ziel als Ziel nehmen sollte, sondern gleich alle Hindernisse miteinbeziehen, habe ich nach erfolgloser Google-Suche hier gepostet.
Grüße
Hartmud-
Hallo
wie sieht diese bisher aus?
Ich habe einen sehr ähnlichen Lösungsansatz wie Rabby verfolgt. [...]Dabei ist mir klar geworden, dass der Ansatz, immer nur in Richtung Ziel zu gehen falsch ist.
siehe auch mein Extrembeispiel :-)
Als mir klar wurde, das ich am Anfang nicht das Ziel als Ziel nehmen sollte, sondern gleich alle Hindernisse miteinbeziehen, habe ich nach erfolgloser Google-Suche hier gepostet.
befolge die Hinweise von Cruz. Der Dijkstra-Algorithmus sollte Dich sicher zum Ziel führen. Dein Hauptproblem reduziert sich somit auf die Erstellung des gewichteten Graphen. Deinem "Hindernis" entsprechen, soweit ich das sehe, allein vier Knoten.
Freundliche Grüße
Vinzenz
-
-
-
Howdy Hartmud,
ich habe gerade an einem theoretischen Problem zu knabbern.
Ich will in PHP die kürzeste Strecke von einem Punkt A(x/y)
zu einem Punkt B(x/y), vorbei an rechteckigen Hindernissen
(x1/y1/x2/y2). Meine bisherige Umsetzung macht noch viele
Umwege ;)Kurze Frage in den Raum geworfen:
Auf was bezieht sich dein Koordinatensystem?[ ] a) Auf Geographische Punkte?
[ ] b) Stern Positionen?
[ ] c) Auf ein Bild?
[ ] d) Auf ein Bildschirmlabyrint?
[ ] e) Was ganz anderes, naehmlich ______gruesse aus'm ruhrpott
jens mueller--
As long as a single mind remembers, as long as a single heart
beats with passion, how can a dream die?
\//_ Live long and prosper -
hallo,
interessante aufgabe!
ich würde spontan sagen, dass Du zuerst prüfen müsstest, ob das rechteck überhaupt "im weg" ist. wenn ja, so gehe am besten den "kürzersten" weg entlang an den rändern des rechtecks. also wenn es derartig aussehen würde:/B
...../...
. .
.../.....
/
/
Aalso in dem fall würd ich laut algo. links rum gehn; auch wenns in dem fall egal, wie rum man geht...
\B
\ .........
. .
.....|...
|
|Ain dem fall aber rechtsrum. also wo eben die strecke von dem schnittpunkt bis zur (nächsten) ecke am kürzesten ist.
mir fällt kein fall ein, wo dieses verfahren "falsch" wäre; schlechtestenfalls eben wie beim 45° winkel im 1. beispiel, also gleich lang.dann eben bis zu derjenigen ecke hinspazieren, wo eben wieder sichtkontakt/ein direkter weg zum zielpunkt besteht.
und da bist Du.
soviel zu meiner theorie. algo gibts keinen fertigen von mir. sorry...
-
Hallo rabby,
ich würde spontan sagen, dass Du zuerst prüfen müsstest, ob das rechteck
_ein_ Rechteck sollte ja auch kein Problem darstellen. Laut Ausgangspostings geht es um mehrere Hindernisse - und da kann es durchaus zielführend sein, zuerst eine völlig andere Richtung einzuschlagen. Stell' Dir vor, Dein Ausgangspunkt liegt in einer Sackgasse, der Zielpunkt hinter der abschließenden Mauer. Im ersten Schritt musst Du Dich vom Ziel entfernen, um den kürzesten Weg zu nehmen.
mir fällt kein fall ein, wo dieses verfahren "falsch" wäre; schlechtestenfalls eben wie beim 45° winkel im 1. beispiel, also gleich lang.
Dein Verfahren ist sicherlich das Grundverfahren, um an einem Hindernis vorbei zu kommen. Nun gilt es nur noch, den kürzesten Weg insgesamt zu finden.
Freundliche Grüße
Vinzenz
-
wenn er sich intensiv damit auseinandersetzen will, kann er sich mal schlau machen zum begriff "algo. der ameisen", der wohl fortschrittlichsten methode aktueller routenplaner...
-
wenn er sich intensiv damit auseinandersetzen will, kann er sich mal schlau machen zum begriff "algo. der ameisen", der wohl fortschrittlichsten methode aktueller routenplaner...
Jup, guter Vorschlag, als Einstiegspunkt evt. die Wikipedia: Ant Colony Optimization.
MfG
Rouven--
-------------------
ie:| fl:| br:> va:| ls:& fo:) rl:( n4:{ ss:) de:] js:| ch:? mo:} zu:| -
Hallo rabby,
wenn er sich intensiv damit auseinandersetzen will, kann er sich mal schlau machen zum begriff "algo. der ameisen", der wohl fortschrittlichsten methode aktueller routenplaner...
ein interessanter und dennoch nicht zielführender Vorschlag: Es geht nicht um einen *guten* Weg, es geht um den kürzesten. Das ist ein riesiger Unterschied.
Die Hinweise von Cruz in https://forum.selfhtml.org/?t=130543&m=843816 und https://forum.selfhtml.org/?t=130543&m=843818 halte ich deswegen für relevanter für die Aufgabenstellung.
Freundliche Grüße
Vinzenz
-
-
-
Hallo,
erstmal vielen Dank für die zahlreiche Hilfe.
Mir ist bei euren Antworten aufgefallen, dass ich noch ein paar wichtige Informationen unterschlagen habe. Zum einen ist es nicht möglich "schräge" Linien zu benutzen, also immer nur senkrechte oder waagrechte Linien (Wendewinkel von 45°). Es geht bei diesem Problem nicht um Sternbilder, sondern letztendlich stellt später jeder Punkt im Koordinatensystem ein Pixel dar.
Grüße
Hartmud
(Ich bin mit meinen vielen Phantasienamen etwas durcheinander gekommen ;))-
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-
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-
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.000das macht schon einen fetten Unterschied.
Gruß
Cruz-
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 ;)-
Hallo _meine_ Jasmin :),
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.
Das kann wohl nicht so ganz stimmen, denn
n+n/2*(n-3) = 2n/2(n-3) = n/n-3
aber
n^2-n / 2 = n(n-1)/2
ich sehe beim besten Willen nicht wie sie gleich sein sollen.
...die prüft, ob das übergebene Objekt im Hinderniss liegt. Dazu muss natürlich auch wieder jede Kante geprüft werden.
Ich habe so ein jucken im Nacken, dass man die Einschränkung auf Rechtecke irgendwie ausnutzen kann, sodass man mit weniger Operationen testen kann, ob ein Liniensegment das Rechteck schneidet.
Gruß
dein Cruz
(hoffentlich bist du wenigstens kein Typ)-
Hallo Cruz.
n+n/2*(n-3) = 2n/2(n-3)
Nein, nein! Irgendjemand hat halt mal festgelegt das Punkt vor Strich gilt. Deswegen brauch ich oben keine Klammer machen.
Zur Veranschaulichung noch mal mit richtigen Formeln:
[latex]n+{n \over 2} \not= {2n \over 2}[/latex]ich sehe beim besten Willen nicht wie sie gleich sein sollen.
naja, es kommt immerhin das Gleiche raus. Bei meinen Rechtkünsten wäre ich auch vorsichtig, aber ich ja meinen CAS.
Gruß
dein Cruz
(hoffentlich bist du wenigstens kein Typ)Wir beenden das jetzt! ;)
Grüße
Jasmin
-
-
-
-
-
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
-
-
-
-
Hallo Jasmin,
wenn man es professionell macht, egal in welcher Sprache, dann berechnet man erstmal den Sichtbarkeitsgraphen.
http://www.geometrylab.de/VisGraph/VisGraph.html
Danach sucht man mit dem Dijkstra Algorithmus auf den Sichtbarkeitsgraphen einen kürzesten Weg.
http://www.cs.umd.edu/~shankar/417-F01/Slides/chapter4a-aus/sld012.htm
Gruß,
Cruz -
Ein anderer sehr guter Ansatz ist ein sogenannter Shortest Path Map. Das hier sollte anschaulich klar machen was es ist:
http://www.geometrylab.de/Flash/ContDijkstra.html
Definition und Algorithmus suchst du bitte selber raus.
Cruz