## 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 *v _{0} = a, v_{1},
, v_{i} = r,
, v_{n} = b *from

*a*through

*r*to

*b*. This is the edges of the funnel

*F*.

We project
each segment *v _{j}v_{j+1}*,

*j = 0,1, , n-1*to the window

*ab*. There are intersections of the projected segments and the window, there be

*x*. Each projected segment

_{0}= a, x_{1}, , x_{i-1}, x_{i+1}, , x_{k}= b*v*

_{j}v_{j+1}*has an angle*

*φ*

_{j}*= angle(b, x*with the window in the intersection, and

_{j}, v_{j}), j = 1,2, , i-1, i+1, , k-1*φ*. The outward convexity of the paths

_{0}= angle(b, a, v_{1}), φ_{k}= angle(a, b, v_{k-1})*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 = x*.

_{j}2.
*φ _{j}*

*< π/2*and

*φ*, then

_{j+1}> π/2, 0≤j≤k-1*c*is the foot of the perpendicular from

*v*to the window.

_{j+1}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 *q _{1}* and

*q*. We search a Shortest Inspection-Path

_{2}*SIP(s,q*, that

_{1},q_{2})*q*and

_{1}*q*are visible.

_{2}Do step 1. We
get two windows *w _{1}* and

*w*, and the two optimal points

_{2}*c*and

_{1}*c*on them. If the path w.o.l.g

_{2}*SIP(s,q*crosses the window

_{1})*w*, then the

_{2}*SIP(s,q*is the

_{1})*SIP(s,q*. When not, we do it the following way:

_{1},q_{2})Compute the
funnel *G* between *w _{1}* and

*w*. First we take window

_{2}*w*and mirror the funnel

_{1}*G*on to another side of

*w*, so that

_{1}*w*will be the symmetry axis of the two funnels. Compute the shortest path from

_{1}*s*to mirrored

*w*with the strategy with one target. We do the same with

_{2}*w*as the symmetry axis, and become the shortest path from s to mirrored

_{2}*w*. We put the segments of the two paths in the mirrored funnel back into the original funnel

_{1}*G*, and take the shorter path. This path is the path

*SIP(s,q*that we searched for.

_{1},q_{2})Literatur:

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