Lets say I have 30 ports on the west of an island, and 30 on the east, and need to calculate all possible shipping distances between each and every port, with the routes having to steer around the geography of the island, which I have as a polygon.
I could digitise by hand but this would take an immense amount of time, so ideally I would like to get ArcGIS to calculate these routes for me by connecting all the points with polylines, but with the polygon as a barrier the polylines have to avoid rather than simply connecting in a straight line over the land (polygon).
As far as I can see in Network Analyst, if I had already had a network of potential routes, it would give me the shortest route option and take into account the polygon barrier. I could create a basic 'rough' network based on a vector grid, and get it to give me routes from this, but is there a more elegant solution? It doesn't seem like it should be an unusual task, but I can't find an existing solution?
Any ideas?
Best Answer
This is an instance of a shortest path problem: given a set S of polygonal "obstacles" (considered as open point sets), a start point p, and an end point q, to find a shortest path from p to q that does not intersect the interior of S.
Such problems are solved by first constructing the "visibility graph" of S. One first proves that any shortest path from p to q is piecewise locally geodesic and that any interior vertices must be vertices of S. (This is easy to see.) The visibility graph of S is a graph G on the nodes of S; its edges consist of all pairs of nodes that can "see" each other: that is, the geodesic between those nodes does not intersect the interior of S. A shortest path therefore can be found by applying any shortest-path algorithm (such as Dijkstra's) to the network defined by the visibility graph G.
This example of a visibility graph (from Carnegie Mellon University's CS department) depicts polygonal obstacles, a universal surrounding polyline, and the visibility graph determined by all of them. Any shortest route between "start" and "goal" must travel along the line segments in the graph, thereby reducing the problem to a standard network algorithm.
Because Network Analyst (and much other software) already can find shortest routes on networks, it remains only to construct the visibility graph for this problem: namely, for the polygonal island and a collection of objects (outside the island's interior) representing the ports. I am pretty sure there is no ESRI software to construct visibility graphs (although it would not be hard to implement good algorithms in Python, so such tools might exist). A Google search finds a (free open source) GRASS implementation in v.net.visibility.
Comments
I suspect any implementation you might find will be Euclidean--that is, it will use projected coordinates--but I see no obstacles to creating a spherical or even ellipsoidal implementation; the ideas are the same and the algorithms should be the same, too. This could be an important consideration for computing shortest long-distance shipping routes, for instance.
Alternatives
It is possible to solve this problem with existing ESRI software using "cost distance" calculations on a grid. (Spatial Analyst is needed for this solution.) The distances might not be very accurately calculated and the routes themselves will be off a little due to inherent discretization error (which cannot be reduced by decreasing the cellsize, unfortunately). The optimal vector-based solutions do not take much more than O(N log(N) +K) time for N vertices and K edges in the visibility graph, which will be a huge computational advantage compared to the gridded solution. If, however, a suboptimal solution is coded (in GRASS or elsewhere), the raster approach could be competitive with the visibility graph approach. Benchmark any solution with small-scale calculations before committing a large project to it.
References
de Berg et al., Computational Geometry, 2nd Ed. Springer (2000). Chapter 15.
S.K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM J. Computing, 20:888-910 (1991).
J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pp 508-517 (1993).