Shortest Path Queries in a Simple Polygon

(Hit reload after you closed the applet window before you hit the Start button again)

How to use the applet

First enter a simple polygon in the polygon editor. (The polygon cannot be changed after that, but you can erase it via the popup menu to enter a new one.) Once the polygon is closed the applet shows the triangulation, the dual graph and the factor graph. A click on Fit fits the screen to show the polygon and the factor graph.

Whenever you click on any two points inside the polygon, the applet computes the shortest path between these two points.

The factor graph

Click on any element of the factor graph to highlight the respective object inside the polygon. The convex chains of the hourglasses are shown in bold red. Note that a convex chain can consist of only one point.

The radio buttons

There a three different ways to show a path:


[1]:Leonidas J. Guibas and J. Hershberger. Optimal Shortest Path Queries in a Simple Polygon. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 50-63, 1987.
[2]:J. Hershberger. A new data structure for shortest path queries in a simple polygon. Inform. Process. Lett., 38: 231-235, 1991.