 |
|
|
|
|
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.
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.
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.
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.
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).
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 |
