Exploring a polygon

Sorry, this WWW browser does not seem to understand Java applets. 

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.

The strategy:

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:

Current Status

The 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