Introduction

The applet “Inspection Path” has two modes - for one and for two query points.
There are also two submodes for running the chosen algorithm - manually (step by step), and automaticaly (with a one-second pause between the steps).

In the first mode, for two given points (a source and a query points), the program computes the shortest path from the source point to some other point in the polygon from that the query point is visible.
In the second mode, for three given points (a source and two query points), the program computes the shortest path from the source point to some other point so that the two query points become visible along this path.

The algorithm is described in the 2005 paper “Shortest Inspection-Path Queries in Simple Polygons” by Christian Knauer and Günter Rote.

User controls

At the start the user can select the mode - one or two query points.
Then a simple polygon should be drawn and after that the source and the query point(s) can be chosen through simple mouse clicks. The shape ot the polygon can be changed by drag and drop only if there is no source point already present.
There is a possibility to delete the polygon or the points through a context menu.
After the points are chosen, the algorithm gets executed and the user can now cycle through the steps (manually or automaticaly) in order to view them.
The source and the query points can be dragged at every time, so one can see how the solution dynamicaly changes.

Algorithm description

Strategy, when just one target point

Note V(q) the sub polygon, where q is visible from every point inside V(q) and r is the lowest common ancestor (LCA) of the two end points of the window w(q) in the shortest path tree T.

The window w(q) = ab be a segment between V(q) and the remaining polygon P - V(q), i.e. the common edge of V(q) and P - V(q). The points a and b are the end points of the window and the point a should be the nearest point to q.

The windows in reference to q can be more than one. If s inside of P – V(q), then the nearest window, which the SP(s,q) will through this, is the, what we consider. The others are not taken into consideration.

Step 1:

 Compute the window ab that separates s from V(q) along with the funnel base LCA r.

1.       Compute the shortest path tree T , the shortest path map M.

2.       Compute a ray-shooting from q through the point a (draw window).

3.       Preprocess T to support LCA-queries.

The funnel F is based on r and ends window ab. The funnel base r consists of the shortest path SP(s,r) from s to r and the funnel F.

Step 2:

Compute the optimal point c on w(q).

We denote a polygon chain v0 = a, v1, … , vi = r, … , vn = b from a through r to b. This is the edges of the funnel F.

We project each segment vjvj+1, j = 0,1, … , n-1 to the window ab. There are intersections of the projected segments and the window, there be x0 = a, x1, … , xi-1, xi+1, … , xk = b. Each projected segment vjvj+1 has an angle φj = angle(b, xj, vj), j = 1,2, … , i-1, i+1, … , k-1 with the window in the intersection, and φ0 = angle(b, a, v1), φk = angle(a, b, vk-1). The outward convexity of the paths P(r, a) and P(r, b) implies that the sequence φj, j = 0,1, … , k is increasing. As a consequence we can characterize the optimal contact point c in the following way:

1.       φj = π/2 for some 0≤j≤k. In this case, c = xj.

2.       φj < π/2 and φj+1 > π/2, 0≤j≤k-1, then c is the foot of the perpendicular from vj+1 to the window.

3.       φ0 > π/2, then c = a.

4.       φk > π/2, then c = b.

The path SP(s,c). through r is the path, that we searched. We call that Shortest Inspection-Path SIP(s,q).

Strategy, when just two target points

There are two target points q1 and q2. We search a Shortest Inspection-Path SIP(s,q1,q2), that q1 and q2 are visible.

Do step 1. We get two windows w1 and w2, and the two optimal points c1 and c2 on them. If the path w.o.l.g SIP(s,q1) crosses the window w2, then the SIP(s,q1) is the SIP(s,q1,q2). When not, we do it the following way:

Compute the funnel G between w1 and w2. First we take window w1 and mirror the funnel G on to another side of w1, so that w1 will be the symmetry axis of the two funnels. Compute the shortest path from s to mirrored w2 with the strategy with one target.  We do the same with w2 as the symmetry axis, and become the shortest path from s to mirrored w1. We put the segments of the two paths in the mirrored funnel back into the original funnel G, and take the shorter path. This path is the path SIP(s,q1,q2) that we searched for.

Literatur:

[1]:C. Knauer, G. Rote, Shortest Inspection-Path Queries in Simple Polygons, April 2005