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

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

Путь должен быть:

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

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

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

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

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

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

Google для "кратчайшего пути Евклида". Wikipedia также имеет некоторую информацию

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

http://en.wikipedia.org/wiki/Euclidean_shortest_path

Ответ 4

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

Ответ 5

Береговую линию высокого разрешения можно найти на сайте NOAA.

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