我面临着一个看似棘手的挑战，那就是设法找到一条从一个海港到另一个海港的海上道路。最终的目的是将其绘制在google（或bing）地图上作为多段线。
路径需要：
是有道理的，因为船不能越过陆地（显然）
不要离海岸线太近。船不能离海岸那么近
不要太复杂。它将被绘制在谷歌地图上，这样一条2000点的折线就不需要了。
最短，但不能牺牲以上三点
所以，我的第一个想法是获得世界各地海岸线的数据。这样的东西是可用的。但不幸的是，它是不完整的。here显示了这些数据以及加勒比群岛等岛屿的海岸线缺失。
我还考虑了地理编码（不够可靠，而且我会通过成千上万的请求来绘制路线）
我的下一个想法是用谷歌地图测试一个点是否是蓝色的。OpenStreetMap是一个很棒的.net映射组件，它允许我创建一个位图来显示它所呈现的内容并测试像素的颜色。
第一个问题是，这个命中测试的精度只有和我测试的图像的分辨率图像一样好。对于彼此靠近的端口，这对于更远的端口来说是很好的，精度会受到影响。
第二个问题，假设我使用某种“蓝色像素测试”方法，是什么样的算法适合寻找路线。GMaps.NET看起来很有希望，但我不知道如何把这条路从“存在”推到靠近海岸的地方。也不该如何减少折线的复杂性。
所以…欢迎输入：想法、想法、链接、示例代码等。谢谢。
（我要补充的是，这是一个旅游网站。准确度不太重要，我没有指导运输或任何事情）
最佳答案
为了简化从a*搜索中得到的多段线，可以使用Douglas-Peucker等算法。另请参见此引用列表：http://maven.smith.edu/~orourke/TOPP/P24.html。
另一种想法：通常应用a*的方法是将每个像素视为可能的状态（位置），但是没有理由不使用像素的子集作为可能的状态。如果使起点和终点附近的状态密度较高，而远离任一终点的状态密度较低，则会自动获得以短而精确的移动开始和结束的路径，但中间有长而直的线段（例如，当穿越太平洋时）。如果你这样做，你可能还想增加土地附近位置的密度。
另一个可能的a*tweak：你可以将“当前方向”合并到状态中，并惩罚导致方向改变的动作。这会在你的道路上产生很长的直线。这将使你的状态空间乘以8，但这可能是可以忍受的。因为您只是增加了一个解决方案的成本，所以您通常使用的直线到目的地的启发式方法对于这个新的成本函数仍然是可接受的，因此不会出现复杂的情况。
关于algorithm - 查找从沿海点A到沿海点B的海路，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8120594/