查找到沿海B点从沿海点的路径海上 [英] Find path by sea from costal point A to costal point B
问题描述
我有试图找出一条路径，通过海运，从一个海港向另外一个海港看似棘手的挑战。最终目标是绘制这对谷歌（或Bing）地图的折线。
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.
的路径需要：
- 是合理的，因为船不能走土地（显然）
- 在不运行太靠近海岸线。船舶不能走那么远接近岸边
- 不要太复杂。这是怎么回事谷歌地图绘制所以2000点的折线不会做。
- 是最短的，而不是在上述三点为代价
所以，我的第一个想法是获得在世界各地的海岸线数据。这样的事情是href="http://www.ngdc.noaa.gov/mgg/shorelines/gshhs.html" rel="nofollow">此处提供
So, my first idea was obtain data on coast lines around the world. Such a thing is available here. Unfortunately it's incomplete however. OpenStreetMap shows this data and shorelines for things like Caribbean islands are missing.
我也想过地理编码（没有足够可靠的，再加上我将通过数千烧请求试图绘制路线）
I also thought about Geocoding (not reliable enough plus I would burn through thousands of requests trying to plot a route)
我的下一步的想法是某种方式使用谷歌地图和测试，如果一个点是蓝色或没有。 GMaps.NET ，一个伟大的.NET Mapping组件，让我通过创建一个位图来实现这一目标它所呈现和测试像素的颜色
My next idea was to somehow use Google Maps and test if a point is blue or not. GMaps.NET, 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.
第一个问题的是，这个命中测试的精度只有一样好，我测试的图像的高分辨率图像。对于彼此靠近港口，这是罚款端口渐行渐远，精度会受到影响。
First problem 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.
问题二，假设我用某种形式的'蓝色像素测试的方法，就是算法是正确的查找路径。该 A *算法看起来很有希望，但我不知道如何推动路径出从福利到附近的海岸。也没怎么减少折线的复杂性。
Second problem, assuming I use some kind of 'blue pixel testing' method, is what algorithm is right for finding a route. The A* algorithm 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.
所以... 任何输入：观念，思想，链接，样品code等将受到欢迎。谢谢你。
So ... any input: ideas, thoughts, links, sample code, etc would be welcome. Thanks.
（我要补充一点，这是一个旅游网站，准确度不是太重要，我不是指挥船或任何东西）
(I should add that this is for a travel site. Accuracy isn't too important, I'm not directing shipping or anything)
推荐答案
要简化你如获得折线A *搜索，您可以像使用道格拉斯 - 普克算法。另请参见参考文献列表： http://maven.smith.edu/~orourke/ TOPP / P24.html 。
To simplify the polyline you get from e.g. A* search, you can use an algorithm like Douglas-Peucker. See also this list of references: http://maven.smith.edu/~orourke/TOPP/P24.html.
另外一个设想：申请A *是考虑每一个像素作为一个可能的状态（位置），但没有理由你不能使用像素的子集的常用方法作为可能的状态来代替。如果您在开始部分国家和端点高的密度，和国家远离两个端点低的密度，那么你会自动获得开头的路径和短端，precise动作，但有长直线段在中间（如穿越太平洋的时候）。如果你这样做，你可能想也增加了近地位置的密度。
Alternative idea: The usual way to apply A* would be to consider each pixel as a possible state (position), but there's no reason why you couldn't use just a subset of the pixels as possible states instead. If you make the density of states near the beginning and endpoints high, and the density of states far from either endpoint low, then you'll automatically get paths that begin and end with short, precise movements, but have long straight segments in the middle (e.g. when crossing the Pacific). If you do this, you might want to also increase the density of positions near land.
另一种可能的A *的调整：：您可以将电流方向进入状态，和惩罚动作，导致方向的改变。这往往会产生路径长直线。这将成倍增加你的状态空间8，但是这可能是可以忍受的。因为你只需要添加到解决方案的成本，你通常会使用直线到目的地启发式仍然可以受理这个新的成本函数，所以没有出现并发症出现。
Another possible A* tweak: You can incorporate "current direction" into the state, and penalise movements that cause a change in direction. This will tend to produce long straight lines in your path. This will multiply your state space by 8, but that's probably bearable. Because you're only adding to the cost of a solution, the straight-line-to-destination heuristic you would normally use remains admissible for this new cost function, so no complications arise there.
这篇关于查找到沿海B点从沿海点的路径海上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
