查找从沿海点A到沿海点B的海路 [英] Find path by sea from coastal point A to coastal point B

问题描述

我面临着一项艰巨的挑战，那就是试图通过一条海路，从一个海港到另一个海港，寻找一条路径。最终目标是将其作为折线绘制在Google（或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.

路径需要：

• 有道理，因为船不能越过陆地（显然）


• 不要过分靠近海岸线。船不能走得那么远


• 不要太复杂。它会被绘制在Google Maps上，所以不会有2000点的折线。


• 最短，但不能以牺牲上述三个点为代价

• Be plausible, as a ship can't go over land (obviously)
• Not run too close to the coast line. Ships can't go that far near to shore
• Not be too complex. It's going to be plotted on Google Maps so a 2000 point polyline wont do.
• Be the shortest, but not at the expense of the above three points

因此，我的第一个想法是获取世界各地海岸线的数据。可以在此处使用。不幸的是，它并不完整。 OpenStreetMap 显示此数据和海岸线，例如加勒比海岛屿缺失之类。

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也考虑过地理编码（不够可靠，再加上我会烧掉成千上万的尝试绘制路线的请求）

I also thought about Geocoding (not reliable enough plus I would burn through thousands of requests trying to plot a route)

我的下一个想法在某种程度上是使用Google地图并测试一个点是否为蓝色。 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.

所以... 任何输入：想法，想法，链接，示例代码等都是欢迎。谢谢。

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 *搜索中，您可以使用 Douglas-Peucker 这样的算法。 。另请参阅以下参考列表： 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 *的方法是将每个像素都视为一个像素可能的状态（位置），但是没有理由为什么不能只使用像素的一部分作为可能的状态。如果您使起点和终点附近的状态密度较高，而远离任一终点的状态密度较低，那么您将自动获得以短而精确的运动开始和结束的路径，但中间有较长的直线段（例如，穿越太平洋时）。如果这样做的话，您可能还希望增加陆地附近位置的密度。

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.

这篇关于查找从沿海点A到沿海点B的海路的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！