Online-Kernfinden in einfachen Polygonen

Bedienung des Applets

Das Applet beinhaltet einen Editor, mit dem auf einer Zeichenfläche ein einfaches Polygon erstellt werden kann. 

Einfach bedeutet hier:

Im Editor kann das Polygon zunächst aus beliebigen einzelnen Eckpunkten und Kanten/Segmenten zusammengefügt werden.

Sobald ein Linienzug zu einem einfachen Polygon geschlossen wird, verschwinden alle übriggebliebenen Punkte und Segmente, und nur das einfache Polygon bleibt übrig.

In diesem geschlossenen Polygon werden nun der Kern und der Pfad zum Kern vom Startpunkt eingezeichnet.

Auch nach dem Schließen des Polygons kann dessen Gestalt weiterverändert werden; der Editor erlaubt neben dem Verschieben von Eckpunkten, Kanten oder des gesamten Polygons auch das Rotieren, Skalieren oder Scheren des Polygons in einem Kontextmenü, das sich bei einem Klick auf das Polygon mit der rechten Maustaste öffnet.
Eckpunkte und Kanten können auch gelöscht und neue hinzugefügt werden.

Nach jeder Veränderung des Polygons wird dieses - sofern geschlossen -jeweils neu gezeichnet, so dass Änderungen des Kerns und des Pfades sofort sichtbar werden.


Berechnung des Pfades

Dieses Applet zeichnet den Pfad von einem Bezugspunkt zum Kern in einem Polygon.

Der Pfad wird mit Hilfe des CAB (Continuous Angle Bisector) Algorithmus berechnet und geht vom Startpunkt zum Kern und von dort direkt zu dem Punkt des Kerns, der der Startposition am nähesten ist.

Hierfür berechnet der Algorithmus kontinuierlich einen Gaining Wedge - Geraden zur linkesten rechten reflexen Ecke und zur rechtesten linken reflexen Ecke - und bewegt sich entlang seiner Winkelhalbierenden. Wenn der Gaining Wedge nur eine Ecke hat (weil es z.B. keine rechteste linke reflexe Ecke gibt), bewegt er sich im Kreis um diese Ecke.

Droht der Agent das Polygon zu verlassen oder wenn sein nächster Schritt dazu führen würde, dass er eine Ecke aus den Augen verliert, so bewegt er sich stattdessen entlang der (Projektion der) Kante, die dieses Ereignis ausgelöst hat.

Über das Rechtsklick-Menü kann man die grauen Hilfslinien (zeigen, wo sich der Gaining Wedge ändert) ein- und ausblenden. Ausserdem kann man statt des Pfades auch nur den Gaining Wedge der momentanen Position anzeigen lassen.

[Applet kann nicht gestartet werden]

Das geschlossene Polygon wird in grau dargestellt.
Der Kern wird in grün gezeichnet.
Der Pfad und der Endpunkt werden in blau gezeichnet.
Der Startpunkt ist in rot dargestellt.