Поиск похожих путей к карте

Я ищу алгоритм, который при задании определенного маршрута на карте с такими атрибутами, как уклон / расстояние / форма / и т. Д., Может найти маршрут, который похож (с точки зрения атрибутов), но начинается в другой точке или в другом регионе земного шара.

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

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

Соответствие карты отличается от того, что вы ищете. Mapmatching - это правильный способ сопоставления gps-наблюдения с погрешностью с линейной сетью улиц. Ваш вопрос также не имеет ничего общего с точками GPS. Потому что вы хотите сравнить шаблон статических маршрутов (не временных) и найти похожие. Что вы ищете, так это линейное соответствие (в смысле ГИС, а не машинного обучения) соответствия . Литература, относящаяся к треку GPS, - это пространственно-временное сопоставление с образцом, которое подпадает под рубрику «Траекторное (пространственно-временное) моделирование».

Для получения дополнительной информации, посмотрите на главу (Траектория Pattern Mining) из книги " Вычисление с пространственной траекторией ". Вы получите много идей о том, как сравнивать и сравнивать (например, по азимуту, длине сегментов, извилистости, билайну и т. Д.) Различные маршруты или траектории.

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

Алгоритм для решения вашего вопроса будет следующим:

1. Растеризуйте исходный маршрут и сделайте так, чтобы каждая ячейка несла параметры в соответствии с вашими спецификациями (наклон / расстояние / форма / и т. Д.). Факт наличия дороги также является параметром. Это становится одномерным списком с n объектами -> routelist (n)

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

3. Начните с ячейки 1,1 в растре a и двигайтесь по всему растру упорядоченным образом.
4. Для каждой ячейки вызывается функция. Эта функция проверяет, соответствует ли ячейка маршрутизатору (0), если так, то такая же проверка выполняется для окружающих ячеек. В случае успеха функция продолжает проверять ячейку на наличие списка маршрутизации (1) и так далее. Если все пути до маршрутизатора (n) пройдены успешно, координаты сохраняются как альтернативный маршрут в routelistcopy (n).
5. Повторяйте, пока не достигнете последнего пикселя в растре.

Выше вы увидите три варианта маршрутов в соответствии с параметрами в Routelist.

Futhermore:

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