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 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 DepthFirstSearch on that dual graph starting at the start point. (Only the part from start to the target point is needed.)
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))
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.
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 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.