I am an intermediate python developer with very limited GIS experience. I have a list of latitude/longitudes of a ship at sea. I need to join them into a polyline using the shortest distance between them to trace the path followed by the ship. However, the path cannot pass over land (for which I have a shapefile). How can I do this? I use Python 2.7.

I am presently not using any GIS software and hope to do the task using the python modules like matplotlib and scipy.

  • 1
    Could you edit the question to include the software and version (if relevant)? That way any answers can be tailored to your needs. Welcome to GIS.SE!
    – Paul
    Aug 20, 2015 at 1:36
  • I would consider a weighted cost distance analysis in raster (with huge cost on land pixels). Following the coast when your shortest path intersect the land will not give the the shortest path.
    – radouxju
    Aug 20, 2015 at 13:57

1 Answer 1


This sounds like a fun problem. I would consider:

  1. Read the land boundary shp file using one of these recipes: How to install Fiona to read Shapefile attributes with OSGeo4W?. It would probably be good to read it into a Shapely geometry. I like using ogr to read shapefiles:
import ogr
import shapely
driver = ogr.GetDriverByName('ESRI Shapefile')
dataSource = driver.Open('landboundary.shp', 0) 
layer = dataSource.GetLayer()
feature = layer[0] # first boundary
geom = feature.GetGeometryRef()
  1. Use NetworkX to build a network of all your lat long ship coordinates, but don't connect coordinates whose straight line connection intersects the land boundary. Here's an example to solve for the intersection of geometries: Shapely LineString and Polygon intersect?.

  2. Then compute the least cost path using NetworkX with distance as the cost. The LCP won't cross over land because those nodes are not connected.

Also, just fyi, shapely geometries convert to WKT (well known text which is a text-based format) like this, myShapelyGeometry.wkt, which is very easy and intuitive to parse and use how you want.

Edit: Just some extra info: To compute the distance between two lat long coords, you can use pyproj:

import pyproj
geod = pyproj.Geod(ellps='WGS84')
_,_,distance = geod.inv(long_start,lat_start,long_end,lat_end)

Also, you can start a networkx graph like:

import networkx
graph = networkx.Graph()
graph.add_edge('coord_a', 'coord_b', weight=distance)
# add more edges in the same way
start_node = find_closest_node(graph, lat_start, long_start)
end_node = find_closest_node(graph, lat_end, long_end)
ship_path = networkx.shortest_path(graph, start_node, end_node)
  • Thanks a lot. That is just the kind of help I needed. Will try this on my developer machine next week. Will request for help if I get stuck. Thanks a lot. Aug 21, 2015 at 16:30
  • Great! Let me know if I can help. It would be good to include any additions in the answer. Also, if you don't mind shelling out some money, here's a good resource where I first learned some of this (I'm not the author): packtpub.com/big-data-and-business-intelligence/…. It's pretty concise, and has a lot of code samples for geospatial stuff, shortest paths, and map matching.
    – user55937
    Aug 21, 2015 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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