Finding shortest path while avoiding polygon features

Question

I'm developing an extension to ArcMap where I have a set of static, concave polygon features and I'm trying to find the shortest path between 2 points without crossing any of the polygons.

Is there an algorithm to do this?

Answer 1

If you have the Spatial Analyst extension, and you don't mind working with raster representations of your data, you can use Cost Path Analysis. The details, and other options can be found within the help topic and the associated sidebar for the help.

Answer 2

I once implemented an algorithm that calculates a polygon that includes the area of a plane (with polygonal obstacles) that can be reached in a certain distance. What helped me most was realizing that shortest path problems in a plane avoiding obstacles can be thought of as visibility problems. While not often discussed in a GIS context, visibility problems are very popular and well documented in computational geometry.

There are two approaches you can take to solve the problem:

1. You can either find the shortest path using just the polygons that are relevant using a spatial index like an R-Tree for your polygons to speed things up.

2. You can build a graph over all your polygons and then find the shortest path within that graph.

Approach 1. is better if you can not keep internal state between the times your algorithm is used. If you have to calculate a lot of shortest paths and the polygons stay the same approach 2. is better.

Approach 1. is what I did for my algorithm. What I did is basically this:

1. Draw a line between the start point and the endpoint.
2. See if it intersects the interior of at least one polygon. If it does not intersect this is your shortest path.
3. If it does intersect take the intersecting segment of polygon which is closest to the start point.
4. Iterate through the vertices of the polygon to the left and to the right side until a line between the vertex and the endpoint does not intersect with the interior of the polygon or until the direct line between the vertex intersects with another polygon. If you intersect with another polygon go to step 2 with that polygon. If not go to step 1 and remember the length between the start point an the vertex that is now the new start point.

Approach 2. is probably better suited for the problem described here and should be easier to implement.

The graph you need for routing in a plane with polygons as obstacles is the visibility graph. The brute force way to build that is quite simple. First you calculate the convex hull of your polygons. Vertices not on the convex hull do not need to be part of the visibility graph. Vertices on the convex hull are the nodes of the visibility graph. The you draw a line between all pairs of vertices an see if that line intersects the interior of a polygon. If the line does not intersect one of the polygons it is an edge in the visibility graph.

You have to add your start and end point to the visibility graph. Then you can use a single source weighted shortest path algorithm. Dijkstra's Algorithm will do the job just fine. If you are expecting a lot of shortest path queries it may be worth it to use an algorithm that calculates all shortest paths and calculate the shortest paths between all pairs of nodes in the visibility graph in advance.

Of course the visibility graph can be used with existing routing tools, so you do not have to implement the shortest path algorithm if you have access to such a tool. (You still face the problem that you have to add your start and end points if they are not already part of the network)

Answer 3

Here is a sample code using ArcObjects to find shortest path (using RasterDistanceOP). This may not be exactly what you want, however it may give you a starting point.

How to find the shortest path using RasterDistanceOp

Answer 4

The first thoughts that came into my head go like this:

1. Determine the maximum bounds of all the features, including start and end points, buffer it out a bit to make sure there's room around all the features. Make a rectangular feature, b, from these bounds.
2. Subtract the blocking features from b.
3. Tesselate b into triangles, making sure the start and end vertices are vertices in this new triangular mesh, m.
4. Generate the Voronoi polygons, t (which should be all triangles) from m.
5. The edges of t form a network on which you can run a shortest-path algorithm.

This may not generate the best shortest path, because it depends on how the tesselator does its job, and in any case will take a centre line rather than the racing line. But it's conceivable that after the shortest path has been generated, you could move or remove vertices, testing each affected edge for intersection with the blocking features, and undoing the operation if it intersects.

Answer 5

The problem is complicated. There is a new generic implementation: Euclidean Shortest Path Algorithm

It works for any sets of meshed surface objects

Answer 6

If you don't mind translating some C, you could try the script on http://alienryderflex.com/shortest_path/