Как найти совпадающие участки на ломаных линиях?

Question

[Евгений]

Есть один или несколько GPS треков, в которых надо найти участки, которые совпадают друг с другом (например возвращался назад по той же самой улице или ходил вокруг дома). Причем совпадения могут быть как между треками, так и внутри одного трека. Подскажите пожалуйста, может есть уже какой-то готовый алгоритм для этого?

Comments

[xmoonlight]

Есть один или несколько GPS треков

так один или несколько?

[Евгений]

xmoonlight, Может быть один, может быть несколько. Суть в том, что надо найти совпадения как внутри трека, так и с другими треками.

Answer 1

[xmoonlight]

Контрольные точки (КТ).

Изменение угла траектории ("излом") более 30°:
1. До 100м (в сегменте пути между КТ, до предыдущей КТ) - ставим контрольную точку.
2. Более 100м - дробим дугу на равные сегменты по 100м контрольными точками.

Иначе - прямая линия.
"Дребезг"/"шум" сигнала в КТ - радиус 10м.

PS: Привязка к дорогам - это уже отдельная тема.

Comments

[Евгений]

Имеется в виду прохождение по точкам трека и по факту фильтрация не сильно влияющих на поворот точек? И дальше эти оставшиеся точки сравниваются между собой на предмет того, не сильно ли они далеко? Если последовательность из нескольких контрольных точек всё ещё вблизи друг от друга, то можно считать что сегменты трека (или разные треки) в этом месте идут параллельно друг другу?

[xmoonlight]

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