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
- Every "leaf" of the factor graph represents a dual graph vertice and therefore a triangle of the triangulation.
- Every "inner node" of the factor graph represents a dual graph edge and therefore a triangulation diagonal.
- Every edge between "inner nodes" in the factor graph represents a preprocessed hourglass between two triangulation diagonals.
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:
- Path: The computed path is shown instantly in black.
- Run: Each step of the concatenation sequence is shown for one second. The already computed, closed hourglass between one point and a principal, separating diagonal is shown in black, while the convex chains of the next to be concatenated hourglass are shown in red. In addition, the respective edges are highlighted in the factor graph.
- Steps: Similar to Run, but you can click yourself through the process with the Next- and Previous buttons.
Literatur:
[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. |