Auf dieser Seite...
(Diese Seite stellt den Anhang zur Wegberechnung dar.)
Endpoint-Berechnung und verschiedene Hindernisformen
Für die Ermittlung der Endpoints eines Hindernisses schrieben wir viele Algorithmen, bis wir die optimale Methode endlich fanden. Betrachtet man das Bild rechts, so liegt die erste Lösung über die Winkel auf der Hand. Man sucht sich einfach die beiden Points heraus, bei denen der Winkel am Ziel maximal ist. Dieses Verfahren hat jedoch den Nachteil, dass der Rechenaufwand nicht linear ist, da jeder Punkt mit allen anderen überprüft werden muss.
- Abb. 3.8 Endpoints
Eine bessere Methode ermöglicht der CCW-Algorithmus von Robert Sedgewick. CCW steht für counterclockwise (engl. entgegen dem Uhrzeigersinn). Mit der Funktion kann überprüft werden, ob einer von drei Punkten links oder rechts neben der Geraden, die durch die beiden anderen Punkte verläuft, liegt. Dies ist für die Lösung unseres Problems sehr hilfreich. Doch auch hier gibt es zwei Varianten.
Bei der ersten wird am Anfang der Point 0 als geschätzter Endpoint (wir betrachten zur Vereinfachung nur Endpoint A, der in diesem Falle Nummer 0 ist) gesetzt. Nun geht die Schleife alle weiteren Punkte durch und überprüft, ob ein Punkt weiter links als Point 0 liegt. Ist dies der Fall, wird der neue Punkt als geschätzter Endpoint gespeichert. Am Ende ist der geschätzte Endpoint der endgültige, da er am weitesten links liegt. Allerdings kommt es bei dieser Vorgehensweise zu Problemen mit speziellen Hindernisformen.
- Abb. 3.9 Hinternis, das das Ziel umschließt
Wir haben zwei Hindernisarten definiert. Die erste Art ist die normale Form und ist in Abbildung 3.8 zu sehen. Die zweite Art hingegen beschreibt Hindernisse, die das Ziel umschließen (Abb. 3.9). Bei solchen Hindernisformen gab es mit der beschriebenen Methode Probleme, weshalb ein weiteres Verfahren programmiert werden musste, das wie folgt funktioniert.
Man denke sich eine Linie vom Ziel zu Punkt 1 (Abb. 3.8). Mit der CCW-Funktion wird überprüft, auf welcher Seite der Nachbarpunkt 2 liegt, in diesem Fall rechts. Dasselbe geschieht mit dem anderen Nachbarpunkt 0, er liegt hier links. Es handelt sich also nicht um einen Endpoint. Starten wir jedoch mit Punkt 0, so stellen wir fest, dass beide Nachbarpunkte auf der rechten Seite liegen - das Zeichen für Endpoint A. Bei Punkt 2 liegen die beiden Nachbarpunkte links - Endpoint B.
Natürlich gibt es auch hier wieder ein Problem. Bei ganz besonderen Hindernisformen, die von der Form her wie auf dem zweiten Bild aussehen, das Ziel jedoch außerhalb liegt, kommt es manchmal vor, dass der Endpoint nicht eindeutig ist. Diese falschen Ergebnisse lassen sich jedoch dadurch erkennen, dass sie auf dem Trace des Hindernisses liegen, sie also nicht direkt vom Ziel erreicht werden können.
Zur Vereinfachung haben wir hier immer nur von einem Endpoint geredet, ein Hindernis besitzt jedoch logischerweise immer zwei, die Berechnung ist also immer für beide durchzuführen.
Trace-Berechnung
Auch die Trace-Berechnung lässt sich auf verschiedene Art lösen. In diesem Fall ist jedoch die Geschwindigkeit von größter Bedeutung, da der Algorithmus oft ausgeführt werden muss.
Die erste Version arbeitete mit Winkeln. Dabei wurden die Winkel zwischen der Geraden durch Ziel und jeweils einen Endpoint und der X-Achse errechnet. Der Wert des Winkels zwischen der Geraden durch Ziel und Roboterposition und der X-Achse muss dann zwischen den beiden vorigen Winkeln liegen, wenn sich der Roboter auf dem Trace befindet. Die trigonomischen Funktionen verbrauchen jedoch viel Rechenkapazität, was das Verfahren langsam macht. Außerdem lässt sich nicht erkennen, ob der Roboter bereits hinter dem Hindernis ist oder noch davor. Nur im letzteren Falle befindet er sich auf dem Trace, obwohl die Funktion dies bei beiden behauptet.
Eine neue Idee wurde durch die Inside-Funktion, ebenfalls von Robert Sedgewick, geweckt. Mit der Inside-Funktion lässt sich überprüfen, ob sich ein Punkt innerhalb eines Polygons befindet oder außerhalb liegt.
Das Bild oben zeigt diese Version grafisch. Der Blaue Bereich wird von den beiden Endpoints sowie fünf weiteren Punkten aufgespannt. Diese fünf Punkte haben alle die gleiche Entfernung vom Ziel und legen so den maximalen Einflussbereich des Hindernisses in der Karte fest. Ob sich der Roboter nun innerhalb dieser Fläche befindet, ist mit der Inside-Funktion einfach zu erkennen.
Auch die umschließende Art der Hindernisse wird wunderbar unterstützt, wie das nächste Bild zeigt.
Auch diese Version ist jedoch zu rechenaufwendig und eigentlich auch zu kompliziert im Vergleich zu der nächsten Methode, auf die wir aus unerklärlichen Gründen erst später gekommen sind...
Hierbei wird einfach überprüft, ob die Verbindungslinie vom Roboter zum Ziel eine Verbindungslinie der Hindernispunkte schneidet. Diese Methode läuft wesentlich schneller als ihre Vorgängerversionen und ist außerdem viel einfacher zu implementieren.