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?
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.
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:
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.
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:
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)
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.
The first thoughts that came into my head go like this:
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.
The problem is complicated. There is a new generic implementation: Euclidean Shortest Path Algorithm
It works for any sets of meshed surface objects
If you don't mind translating some C, you could try the script on http://alienryderflex.com/shortest_path/