Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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? Thanks.

share|improve this question
    
Theoretically speaking, there are infinite number of such routes. What exactly are you trying to do, or what do you wish to achieve? –  Devdatta Tengshe Mar 6 '13 at 9:19
    
For 60 ports, there would be 1770 unique non-replicated non-zero distances to be calculated. As described, I am trying to calculate the distances ships would have to travel between each port. In the real world I would need to consider minimum water depth, but at the moment for proof of concept, I have only listed the island polygon as the only constraint to the ship routes. Apart from avoiding land (the polygon), the polylines just have to connect the points along the shortest route. –  bigjim Mar 6 '13 at 10:18
    
how do you get 1770? n(n/2) gives the number of combinations, but not the number of routes. Or maybe you actually want something else. Just connecting them and avoiding a polygon are two different things. –  Devdatta Tengshe Mar 6 '13 at 10:32
    
Yes, as I say I need to avoid the polygon and not simply connect them which would be very easy - the ships can not sail over land, only around it. If you are familiar with distance matrixes such as found in a road atlas or nautical almanacs, this might help you understand how it is possible to describe distances between one location and many other locations. Apart from that I don't think I can make anything any simpler for you I'm afraid. –  bigjim Mar 6 '13 at 11:22
    
Here is why I am saying there are infinity many routes: Suppose a Ship is sailing from San Fransisco to London; It can pass through the Panama canal, It can pass around Canada in the Arctic ocean. It can sail around South America. There are infinitely many such paths. Distance matrices in Road Atlases, tend to give the shortest path, which tends to be unique. –  Devdatta Tengshe Mar 6 '13 at 11:53
add comment

1 Answer 1

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.

Example

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).

share|improve this answer
    
Thank you for your detailed answer. I had briefly looked at the cost distance tool in Spatial but felt a raster solution was a bit clunky. The biggest issue is that I am faced with this problem in a work situation, where time is money! I think I follow your visibility graph concept and will look into that. –  bigjim Mar 7 '13 at 12:25
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.