title: Find path by sea from coastal point A to coastal point B
body: <p>I have the seemingly tricky challenge of trying to work out a path, by sea, from one sea port to another sea port. The eventual aim is to plot this on a Google (or Bing) Map as a polyline.</p>
  
  <p>The path needs to:</p>
  
  <ul>
  <li>Be plausible, as a ship can't go over land (obviously)</li>
  <li>Not run too close to the coast line. Ships can't go that far near to shore</li>
  <li>Not be too complex. It's going to be plotted on Google Maps so a 2000 point polyline wont do.</li>
  <li>Be the shortest, but not at the expense of the above three points</li>
  </ul>
  
  <p>So, my <strong>first idea</strong> was obtain data on coast lines around the world. Such a thing is available <a href="http://www.ngdc.noaa.gov/mgg/shorelines/gshhs.html">here</a>. Unfortunately it's incomplete however. <a href="http://www.openstreetmap.org">OpenStreetMap</a> shows this data and shorelines for things like Caribbean islands are missing.</p>
  
  <p>I also thought about Geocoding (not reliable enough plus I would burn through thousands of requests trying to plot a route)</p>
  
  <p>My <strong>next idea</strong> was to somehow use Google Maps and test if a point is blue or not. <a href="http://greatmaps.codeplex.com/">GMaps.NET</a>, a great .NET Mapping component, allowed me to achieve this by creating a bitmap of what it renders and testing the color of a pixel.</p>
  
  <p><strong>First problem</strong> is that the accuracy of this hit testing is only as good as the resolution image of the image I test against. For ports close to each other, this is fine for ports further away, the accuracy suffers.</p>
  
  <p><strong>Second problem</strong>, assuming I use some kind of 'blue pixel testing' method, is what algorithm is right for finding a route. The <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm">A* algorithm</a> looks promising, but I'm not sure how to push the path 'out' from the being to near to the coast. Nor how to reduce complexity of the polyline.</p>
  
  <p>So ... <strong>any input</strong>: ideas, thoughts, links, sample code, etc would be welcome. Thanks.</p>
  
  <p>(I should add that this is for a travel site. Accuracy isn't too important, I'm not directing shipping or anything)</p>