Exploring a polygon
This applet demonstrates how an agent has to walk if he wants to move on a shortest route that sees every point inside a simple room, even if the room is unknown before.
Our model is as follows: The simple room is modelled by a simple polygon (simple means: no crossing edges) and the agent is described by a point in the two dimensional sphere. By definition a watchman route inside a simple polygon is a closed route that "sees" every point inside the polygon, i.e. the conjunction of all visibility polygons along the path should cover the whole polygon. So for a given start point our task is to find a watchman route inside a polygon while "walking" through the polygon.
The strategy demonstrated here is an algorithm of Hoffmann, Icking, Klein and Kriegel published in their paper ". An efficient competitive strategy for learning a polygon. Technical Report B 96-01, Freie Universität Berlin, Fachbereich Mathematik, 1996" . This strategy computes the shortest watchman route online.
The strategy explores a given polygon "room by room". That means that during the exploration the polygon is divided into subpolygons, so called "rooms". New detected rooms get stored and explored later. The exploration within the room contains some consecutive "Scout" and "March" phases, appropriate to the strategy's name.
The Scout phase of the algorithm uses arcs to explore hidden parts of the room. The exploration by arcs corresponds to a behaviour people generally choose by intuition in this situation: you approach to the blocking corner by a semicircle. So you have the chance to see the area behind the corner earlier. If you walk straight forward to the corner you must cover the whole distance anytime. In Comparison to that the walk on the semicircle can be only a fraction of the straight forward distance and is at most pi/2-times as long. Thales' theorem about rectilinear triangles in semicircles guarantees that you leave the start corner and approach to the target steadily. Therefore - using arcs, sections of semicircles, the Scout phases explore all blocking corners inside the room.
The task of the March phase is, to go straight forward to the start point of a new Scout phase, if this point is just not visible. Main problem is to notice the straight way and update it in case of an obstacle.
How to use the applet:
When you start the applet you get a simple example. A mouse click on any vertex of the polygon starts the exploration trip. Further examples are available, see the list box on the left.
If you wont to construct your own polygon you have to work as follows:
- to clean the drawboard click on the "Polygon löschen" button. The applet switchs into the paint mode "Polygon zeichnen".
- by mouse clicks (left button) on the drawboard construct the new polygonal chain. Remind, that only clicks are accepted satisfying the roules of a simple polygon.
- to close the polygonal chain to a simple polygon click with the right mouse button anywhere on the drawboard. The two ends of the polygonal chain will be connected. Remind, that the same condition holds: only clicks are accepted satisfying the roules of a simple polygon.
- use the checkbox "Algorithmus ausführen" to switch into the execution mode. Click on any vertex of your polygon to start the algorithm.
Current StatusThe implementation of 'polyexplore' has a bug: sometimes the exploration stops before the whole polygon is explored :-(
Comments may be adressed to:
© 1997 Praktische Informatik VI, FernUniversität Hagen
© 2001 University of Bonn, Dept. of Computer Science I
Urs-M. Bachert, Christian Icking, Tom Kamphans, Elmar Langetepe