Определение общих сегментов маршрута по трекам GPS

Question

Скажем, у меня есть несколько записанных треков GPS. Некоторые из них повторяются по одному и тому же маршруту, некоторые - из совершенно уникальных маршрутов, а некоторые являются разными маршрутами, но имеют общие сегменты.

Учитывая все эти данные, я хочу:

1. определить повторные поездки по одному и тому же маршруту
2. идентифицирует сегменты, которые используются несколькими маршрутами

Полагаю, что 1 действительно является частным случаем 2.

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

Существуют ли опубликованные алгоритмы для этого? Как они работают? Указатели на документы и / или код с благодарностью.

Answer 1

Вы можете использовать гистограмму 3D, чтобы найти наиболее посещаемые точки на карте. Используя это, вы можете получить наиболее часто используемые пути.

Деталь: сохраните счетчик 2D-матрицы и установите его в 0, X [i, j] = 0. Для каждой дорожки увеличивайте X [i, j] s на пути. После того как вы обработали все дорожки, пороговое значение этой матрицы составляет минимальное пороговое значение (какое минимальное количество дорожек должно быть для повторной поездки?).

Некоторые практические детали: Предположим, у вас есть набор точек, через которые проходит путь. Вы можете найти множество точек на пути между двумя такими точками с помощью http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm. Возможно, вы захотите нарисовать «более толстую линию», чтобы учесть шумный характер данных.