查找从沿海点 A 到沿海点 B 的海上路径

Question

我面临着看似棘手的挑战，试图找出一条从一个海港到另一个海港的海上路径。最终目标是将其绘制在 Google（或 Bing）地图上作为折线。

路径需要：

• 合理，因为船不能越过陆地（显然）
• 不要距离海岸线太近。船不能离岸那么远，
• 也不能太复杂。它将在 Google 地图上绘制，因此 2000 点的折线无法完成。
• 做到最短，但不能牺牲以上三点

所以，我的第一个想法是获取世界各地海岸线的数据。这样的东西可以在这里找到。不幸的是，它还不完整。 OpenStreetMap 显示了这些数据，并且加勒比岛屿等地区的海岸线缺失。

我还考虑过地理编码（不够可靠，而且我会消耗数千个尝试绘制路线的请求）

我的下一个想法是以某种方式使用Google地图并测试一个点是否是蓝色的。 GMaps.NET 是一个很棒的 .NET 映射组件，它允许我通过创建其呈现的位图并测试其颜色来实现此目的一个像素。

第一个问题是，此命中测试的准确性仅与我测试的图像的分辨率图像一样好。对于彼此靠近的端口来说，这很好，对于较远的端口来说，精度会受到影响。

第二个问题，假设我使用某种“蓝色像素测试”方法，什么算法适合寻找路线。 A* 算法 看起来很有希望，但我不确定如何将路径从存在中“推出”到靠近海岸的地方。也不知道如何降低折线的复杂性。

所以......任何输入：想法、想法、链接、示例代码等都将受到欢迎。谢谢。

（我应该补充一点，这是一个旅游网站。准确性并不是太重要，我不指导运输或其他任何事情）

Answer 1

这是一个使用 R 的解决方案。可以进一步完善，只需使某些区域对于最短路径算法变得昂贵或便宜即可。例如，排除北冰洋、允许主要河流/运河、指定已知的旅行首选航线。

library(raster)
library(gdistance)
library(maptools)
library(rgdal)

# make a raster of the world, low resolution for simplicity
# with all land having "NA" value
# use your own shapefile or raster if you have it
# the wrld_simpl data set is from maptools package
data(wrld_simpl)

# a typical world projection
world_crs <- crs(wrld_simpl)
world <- wrld_simpl
worldshp <- spTransform(world, world_crs)
ras <- raster(nrow=300, ncol=300)

# rasterize will set ocean to NA so we just inverse it
# and set water to "1"
# land is equal to zero because it is "NOT" NA
worldmask <- rasterize(worldshp, ras)
worldras <- is.na(worldmask)

# originally I set land to "NA"
# but that would make some ports impossible to visit
# so at 999 land (ie everything that was zero)
# becomes very expensive to cross but not "impossible" 
worldras[worldras==0] <- 999
# each cell antras now has value of zero or 999, nothing else

# create a Transition object from the raster
# this calculation took a bit of time
tr <- transition(worldras, function(x) 1/mean(x), 16)
tr = geoCorrection(tr, scl=FALSE)

# distance matrix excluding the land, must be calculated
# from a point of origin, specified in the CRS of your raster
# let's start with latlong in Black Sea as a challenging route
port_origin <- structure(c(30, 40), .Dim = 1:2)
port_origin <- project(port_origin, crs(world_crs, asText = TRUE))
points(port_origin)

# function accCost uses the transition object and point of origin
A <- accCost(tr, port_origin)

# now A still shows the expensive travel over land
# so we mask it out to display sea travel only
A <- mask(A, worldmask, inverse=TRUE)

# and calculation of a travel path, let's say to South Africa
port_destination <- structure(c(20, -35), .Dim = 1:2)
port_destination <- project(port_destination, crs(world_crs, asText = TRUE))

path <- shortestPath(tr, port_origin, port_destination, output = "SpatialLines")
 
# make a demonstration plot
plot(A)
points(rbind(port_origin, port_destination))
lines(path)

# we can wrap all this in a customized function
# if you two points in the projected coordinate system,
# and a raster whose cells are weighted 
# according to ease of shipping
RouteShip <- function(from_port, to_port, cost_raster, land_mask) {
  tr <- transition(cost_raster, function(x) 1/mean(x), 16)
  tr = geoCorrection(tr, scl=FALSE)
  A <- accCost(tr, from_port)
  A <- mask(A, land_mask, inverse=TRUE)
  path <- shortestPath(tr, from_port, to_port, output = "SpatialLines")
 
  plot(A)
  points(rbind(from_port, to_port))
  lines(path)
}

RouteShip(port_origin, port_destination, worldras, worldmask)

Answer 2

为了简化从 A* 搜索中获得的折线，您可以使用类似 道格拉斯-普克。另请参阅此参考文献列表： http://maven.smith.edu/~orourke/ TOPP/P24.html。

替代想法：应用 A* 的通常方法是将每个像素视为可能的状态（位置），但没有理由不能仅使用像素的子集作为可能的状态反而。如果将起点和端点附近的状态密度设置为高，将远离任一端点的状态密度设置为低，那么您将自动获得以短而精确的运动开始和结束，但中间有长直线段的路径（例如穿越太平洋时）。如果这样做，您可能还想增加陆地附近的位置密度。

另一个可能的 A* 调​​整：您可以将“当前方向”合并到状态中，并惩罚导致方向改变的运动。这往往会在您的路径中产生长直线。这将使您的状态空间乘以 8，但这可能是可以忍受的。因为您只是增加了解决方案的成本，所以您通常使用的直线到目的地启发式对于这个新的成本函数仍然是可接受的，因此不会出现任何复杂情况。

Answer 3

第二个问题，假设我使用某种“蓝色像素测试”方法，什么算法适合寻找路线。 A* 算法看起来很有希望，但我不确定如何将路径从实体“推出”到海岸附近。也不知道如何降低折线的复杂性。

首先创建世界的二值海洋图像（白色：是海，黑色：不是海），然后腐蚀该图像。侵蚀后的所有白点均可通航。当然，忽略一两个奇怪的沙洲。

正如您可能猜到的那样，这种方法揭示了寻路中的一个核心问题：大多数船只必须非常靠近陆地才能到达港口，这违反了导航规则。然而，这个问题可以通过在与给定港口相邻的最近的可航行海点开始航行来解决。

Answer 4

如果我是你，我会选择图论方法。您唯一的问题是收集数据库的边缘。如果您有它们，您可以使用 A* 或 Dijkstra 算法来规划最短路线。
不管怎样，如果我认为是正确的，你需要类似于 (Searoutefinder) 的东西，对吗？祝你好运！

Answer 5

这是使用 scgraph 的 Python 方法。理论上，您可以使用 scgraph 来解决各种网络图的最短路径，使用一些经过修改的 Dijkstra 算法，这些算法设计对稀疏图非常有效。

该软件包附带了一些基本的网络图来帮助您入门。有几个海事网络图可供使用。

以下是文档中的一个示例，使用稍作修改（针对反子午线支持进行调整）的 Marnet 数据：

# Use a maritime network geograph
from scgraph.geographs.marnet import marnet_geograph

# Get the shortest path between 
output = marnet_geograph.get_shortest_path(
    origin_node={"latitude": 31.23,"longitude": 121.47}, 
    destination_node={"latitude": 32.08,"longitude": -81.09}
)
print('Length: ',output['length']) #=> Length:  19596.4653
print(str([[i['latitude'],i['longitude']] for i in output['coordinate_path']])) #=> [[...],...]

根据您的绘图需求，您需要为您正在使用的 gis 系统相应地设置坐标路径的格式。

这将产生如下路由：

注：scgraph 产生的长度假设所有非基于网络的地理旅行的迂回系数为 3。这用作一种方式强迫优化算法选择一个与所提供的坐标相当接近但可能不在网络中的网络节点。假设您使用具有海事网络数据的实际海港，这种影响应该是微乎其微的。然而，如果您不小心选择了位于内陆地区中部的港口，则旅程的第一段/最后一段将增加 3 倍的大圆距离。

作为旁注，您可能希望简化最终路由以减少数据开销。减少数据开销的一个好选择是mapshaper（web，cli）。