## Calculating the shortest path in a simple polygon - the Funnel Algorithm

(Please click on the button above to start the applet.)

__Calculating the shortest path in a simple polygon__

Given a closed polygon the shortest path inside that polygon from
a **start** point to a **target** shall be constructed. Those
two points must of course be inside the polygon, too. This path only
consists of segments between start, target and some vertexes of the
outline of polygon. How can these points be connected in the shortest
way with no polygon edges intersecting?

There exist some algorithms to solve this problem - this applet represents the algorithm invented by D.T. Lee and F.P. Preparata in 1984.

Please click on „*Start the algorithm!*“
above to start the applet!

In the lower part of this page one can get a description of the applet.

### The algorithm

The tasks of the algorithm:

Compute the

*triangulation*of the given simple polygon. (using the*Seidel triangulation*: runtime: ~O(*n*))Compute the

*dual graph*of that triangulation. (runtime: O(*n*))Compute the

on that dual graph starting at the start point. (Only the part from start to the target point is needed.)**D**epth**F**irst**S**earch(runtime: O(

*n*))Iteratively add the diagonals that are crossed by the DFS and calculate the funnels that represent the shortest path from start to the end points of the now examined diagonal. (runtime: O(

*n*))

Runtime specifications refer to the size *n*
of the point set.

#### Seidel-Triangulation

Runtime: ~*O*(*n*)

An algorithm that computes the triangulation of a polygon quite
fast is the Seidel-Triangulation. It has a runtime of *O*(*n
log* n*), which is almost linear. More information can be found
in: *Raimund Seidel: A Simple and Fast Incremental Randomized
Algorithm for Computing Trapezoidal Decompositions and for
Triangulating Polygons.*

#### Funnels

Runtime: *O*(*n*)

The shortest path from **start** to **target** can be
computed in *linear runtime* by initiating the funnel exploration at **start **and then
iterativly (in *DFS order*) adding diagonals until finally adding
the **target**. Only the shortest paths from
the temporary start (the *root*) of the funnel to the top of the
funnel, which is always represented by the currently added *diagonal* have to be inspected.
Those shortest paths are framed by the walls of the funnel: every
shortest path to any point on the current diagonal lies inside the
funnel.

When the first diagonal that is visited by the DFS is added, the
left end point is added to the left funnel wall(from the perspective
of start) and the right one to the right funnel wall . So the first
funnel always is a triangle unless start lies on the first diagonal.
When a new diagonal is inserted, there is actually only one new point
added to the funnel (an end point of that diagonal) as the other
point corresponds to one of the end points of the previous diagonal:
*two subsequent diagonals always have one end point in common*.
When that new point has to be added to the left funnel wall, the left
funnel wall has to be examined first (for a point that has to be
added to the right funnel wall this corresponds): the funnel is
scanned from the top (the previous diagonal) to the current root to
find a tangent from the added point to the funnel wall. Those points
that have been unsuccessfully visited will be deleted. So every point
will be visited only once (this leads to the runtime: O(*n*)).

If the root of the current funnel has already been examined and
neither a tangent nor a direct connection to the root has been found,
the search continues at the other funnel wall now going from root to
the other end point of the current diagonal. First the root and then
all following points are added to the shortest path from start to
target until a tangent is found. Such a tangent will usually be found
as the funnel walls are *convex chains*. The point, where the
tangent lies is the new root of the funnel. If none is found and the
other end point of the diagonal is reached, the funnel consists only
of that diagonal and the „*old*“ diagonal end point
is the new root. In that case a concave polygon edge needs to be
by-passed by the shortest path.

At the end, **target** is
added to the left funnel wall and a last funnel exploration takes
place. The complete shortest path now consists first of the temporary
shortest path and second of the final left funnel wall.

### The applet

The start button above opens a separate frame containing the actual application.

In this new window please first draw a simple polygon on the white
drawing area. Redundant points, i.e. points that lie on an edge and like this are unnecessary, will be deleted. The three *zoom* buttons above can be used to zoom
view in or out. A click on **Fit** fits the polygon size perfectly
to the window size.

Once the polygon is closed the applet can show the **triangulation
**(in yellow dotted lines) and the **dual graph **(coloured
blue). Just click on the corresponding Checkboxes in
the lower part of the window.

Please note, that whenever you insert a point on a polygon edge, the applet will not refresh until you move that new redundant point.

To insert the **start** or the **target** point, right-click
inside the polygon and select the corresponding menu item in the
popup menu. Start will be coloured dark green and target will be red.
The *diagonals* of the Seidel triangulation that need to be
crossed by the shortest path from **start **to **target** will
be visible immediately as yellow dashed lines.

Next to the two Checkboxes for the triangulation and the dual
graph, there are three Radio buttons which allow you to select the
way in which the construction of the shortest path should be shown.
You can see the shortest path (always in green) at once by clicking
on **Path**.

If you want to see an automated funnel exploration, click on **Run.**
The funnels pop up in red outlined in white – or if the funnel
corresponds to a diagonal, it will be only a white segment. This kind
of exploration will look quite similar to the picture below, but it
will develop automatically (please do not interrupt the automated
development by clicking anywhere while it runs, this might lead to
multiple automated runs).

By default **Steps** is selected. Whenever you click on **Next**,
the current funnel will become an old funnel in dark red and the next
funnel will popup in bright red. But before that, you will see
blue segments popup, if the old funnel consists of more than a
diagonal and if the new diagonal not only extends one of the old
funnel walls, because it keeps the convex chain convex. Those are the
segments, that are checked for being *tangents* to the funnel
walls.

If a funnel corresponds to one of the diagonals, that diagonal will be overpainted in white, if it is the current funnel or in red, if its a previous funnel.

The previous funnel will become visible in dark red outlined in
red, when you click on **Previous**.

If a previous funnel (in the **Steps** case) is overlapped by
the actual funnel, please note, that the *top* of the previous
funnel always corresponds to the previously entered diagonal and that
side of the old funnel, that stays invisible corresponds to the part
of the current funnel up to the previously inserted diagonal.

### Reference:

D. T. Lee and F. P. Preparata: Euclidean shortest paths in the presence of rectilinear barriers. Networks, 14:393-410, 1984.