Найти путь по морю от прибрежной точки A до прибрежной точки B

Question

У меня, казалось бы, непростая задача: попытаться проработать морской путь от одного морского порта к другому морскому порту. Конечная цель состоит в том, чтобы нанести это на карту Google (или Bing) в виде ломаной линии.

Путь должен:

• Будьте правдоподобны, так как корабль не может пересечь землю (очевидно)
• Не бегите слишком близко к береговой линии. Корабли не могут заходить так далеко от берега
• Не будь слишком сложным. Он будет нанесен на Карты Google, поэтому полилинии в 2000 точек не получится.
• Быть кратчайшим, но не за счет вышеуказанных трех баллов

Итак, моей первой идеей было получение данных о береговых линиях по всему миру. Такая вещь доступна здесь . К сожалению, это не полностью, однако. OpenStreetMap показывает эти данные, а береговые линии для таких вещей, как Карибские острова, отсутствуют.

Я также думал о геокодировании (недостаточно надежно, плюс я бы прожег тысячи запросов, пытаясь проложить маршрут)

Моя следующая идея заключалась в том, чтобы каким-то образом использовать Карты Google и проверить, является ли точка синей или нет. GMaps.NET , замечательный компонент .NET Mapping, позволил мне добиться этого, создав растровое изображение и отредактировав цвет пикселя.

Первая проблема заключается в том, что точность этого теста попадания так же хороша, как и разрешение изображения, которое я проверяю. Для портов, расположенных близко друг к другу, это хорошо для портов, расположенных дальше, точность страдает.

Вторая проблема , если предположить, что я использую какой-то метод «тестирования синего пикселя», это какой алгоритм подходит для поиска маршрута. Алгоритм A * выглядит многообещающе, но я не уверен, как вытолкнуть путь из существа к побережью. Ни как уменьшить сложность полилинии.

Итак ... любой ввод : идеи, мысли, ссылки, примеры кода и т. Д. Приветствуются. Спасибо.

(Я должен добавить, что это для туристического сайта. Точность не так уж важна, я не направляю доставку или что-то еще)

Answer 1

Чтобы упростить ломаную линию, которую вы получите, например, * Поиск, вы можете использовать алгоритм, как Дуглас-Пекер . Смотрите также этот список ссылок: http://maven.smith.edu/~orourke/TOPP/P24.html.

Альтернативная идея: Обычный способ применения A * состоит в том, чтобы рассматривать каждый пиксель как возможное состояние (положение), но нет причины, по которой вы не могли бы использовать только поднабор пикселей в качестве возможные состояния вместо. Если вы сделаете плотность состояний вблизи начальной и конечной точек высокой, а плотность состояний далеко от любой конечной точки низкой, то вы автоматически получите пути, которые начинаются и заканчиваются короткими, точными движениями, но имеют длинные прямые сегменты в середине (например, при пересечении Тихого океана). Если вы сделаете это, вы можете также увеличить плотность позиций рядом с землей.

Еще один возможный трюк A *: Вы можете включить «текущее направление» в состояние и штрафовать движения, которые вызывают изменение направления. Это приведет к появлению длинных прямых линий на вашем пути. Это умножит ваше пространство состояний на 8, но это, вероятно, терпимо. Поскольку вы только добавляете стоимость решения, эвристика прямой линии к месту назначения, которую вы обычно используете, остается допустимой для этой новой функции стоимости, поэтому никаких сложностей здесь не возникает.

Answer 2

Вторая проблема, если предположить, что я использую какой-то метод «тестирования синего пикселя», заключается в том, какой алгоритм подходит для поиска маршрута.Алгоритм A * выглядит многообещающе, но я не уверен, как протолкнуть путь от существа к побережью.Ни как уменьшить сложность ломаной линии.

Сначала создайте двойное морское изображение мира (белый: море, черный: не море), затем сотрите изображение.Все белые точки после эрозии судоходны.Конечно, пренебрегая лишним или двумя песчаными отмелями.

Как вы можете догадаться, этот подход обнаруживает центральную проблему при поиске пути: большинству кораблей приходится держаться достаточно близко к земле, чтобы добраться до порта, нарушая правила навигации.Однако это можно решить, начав навигацию в ближайшей судоходной морской точке, примыкающей к данной гавани.

Answer 3

Вот решение, использующее 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 4

На вашем месте я бы выбрал подход теории графов.Ваша единственная проблема - собрать грани базы данных.Если они у вас есть, вы можете использовать алгоритм A * или Дейкстры для планирования кратчайшего маршрута.В любом случае, если я правильно понял, вам нужно что-то похожее на (Searoutefinder) верно?Удачи!