Кратчайший путь между необработанными географическими координатами и узлом графика

Question

Я реализовал простой алгоритм Дейкстры для поиска кратчайшего пути на карте .osm с Java.

Поиск пути в графе, который создается из файла .osm, работает довольно хорошо. Но если текущее местоположение и / или пункт назначения пользователя не является узлом этого графа (просто необработанные координаты), как мы можем «связать» эти координаты с графом, чтобы заставить поиск пути работать?

Простое простое решение "найти ближайший к узлу текущего местоположения и нарисовать прямую линию" не представляется реалистичным. Что делать, если у нас есть ситуация, как на прилагаемой картинке? (UPD)

Проблема здесь в том, что перед тем, как мы запустим любые «умные» алгоритмы поиска пути (например, Дейкстры), мы «связываем» текущую позицию с графом, но это просто тупая формула (гипотенуза из теоремы Пифагора) о нахождении ближайшего узла с точки зрения географических координат, и эта формула не является «путевой» - она ​​не может принимать во внимание препятствия и типы узлов.

Перефразируя это - как нам найти кратчайший путь между A и B, если B является узлом в графе, а A не является узлом?

Вы слышали о каких-либо других решениях этой проблемы?

Answer 1

Процесс, который вы описываете: « сопоставление карты », и он использует пространственный индекс для поиска ближайшего узла.

Один из распространенных подходов заключается всоздайте quadtree , которое содержит все ваши узлы, затем определите квад, содержащий вашу точку, затем вычислите расстояние от вашей точки до всех узлов в кваде (с учетом того, что продольные градусы короче широтных).Если в кваде нет узлов, вы постепенно расширяете свой поиск.Есть несколько предостережений с квадриями, но это, по крайней мере, должно помочь вам начать.

Answer 2

Если у вас есть ограничения на вашем пути, вам следует рассмотреть возможность использования формулировки линейного программирования той же самой задачи кратчайшего пути.

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

Ваша цель - свести к минимуму сумму расстояния каждого «пути» между начальным и конечным «узлами», определенными в вашем файле .osm.Любые препятствия будут сформулированы как ограничения.Для реализации с Java, см. Ссылку ниже.

http://javailp.sourceforge.net/

Answer 3

На практике я бы просто проигнорировал проблему и использовал предложенный вами алгоритм "прямая линия до ближайшего узла".Пользователь обязан быть как можно ближе к маршрутизируемому объекту.Если первое предположение, которое вы предложили, было ошибочным, пользователь может соответствующим образом изменить начальную позицию.

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

Кстати, этот алгоритм используется OpenRouteService и Google Maps .

Если все еще не уверен, я предлагаю использовать «самую короткую прямую линию, которая не пересекает препятствие».Если этого все еще недостаточно, определите виртуальную сетку, скажем, 5mx5m и ее диагонали.Чем охватить алгоритм кратчайшего пути до достижения вершины графа.

Answer 4

Действительно хороший вопрос!

Quad Tree - это решение, так как вы можете индексировать линии / ребра, а не только узлы.

Но проблемы этого «наивного» подхода заключаются в том, что эти решения требуют большого объема памяти. Например. если у вас уже есть очень большой график для вычисления кратчайшего пути, тогда вам нужно столько же или больше памяти для четырехугольного дерева (или я делал что-то очень глупое).

Одно из решений выглядит следующим образом:

• использовать массив, который является сеткой над используемой областью. Я имею в виду, что вы можете разделить свою область на плитки, и для каждой плитки у вас есть запись массива со списком узлов.
• так что для каждой записи массива у вас будет список узлов в этой плитке. Для ребра вы можете просто добавить оба узла в запись. Будьте осторожны, когда есть ребра, пересекающие плитку, не имея своего узла в этой плитке. Здесь поможет алгоритм BresenhamLine.
• запрос: преобразовать входные данные ala (lat, lon) в число плиток. Теперь получите все точки из массива. Вычислите ближайшего соседа узлов и ребер до вашей точки A , используя евклидову геометрию (что должно быть хорошо, если они не слишком далеко, как в случае ближайшего соседа).

Это описание понятно?

Обновление Теперь реализовано в Graphhopper!

Чтобы получить более эффективное решение для памяти, вы должны просто исключить идентичные узлы для одной записи (плитки).

Немного более сложная техника для уменьшения использования mem: если при обходе графа учитываются границы тайла, можно представить, что граф затем делится на несколько подграфов для этого тайла (т.е. обход графа не достигнет другой подграф в пределах границ тайла). Теперь вам нужны не все узлы, а только узлы, которые лежат в другом подграфе! Это уменьшит использование памяти, но при запросах вам нужно пройти не только один край дальше (как в текущей реализации Graphhopper)! Потому что вам нужно пройти всю плитку - то есть, если границы плиток не превышены.

Answer 5

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

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