Как нарисовать ровный маршрут на карте, имея большое количество GPS-координат с ошибками?

Question

[Илья С]

Мы разрабатываем мобильное приложение, одна из функций которого - отслеживание маршрута пользователя. Приложение просто посылает координаты на сервер, когда пользователь перемещается.
Затем встаёт главная проблема - как по этим координатам нарисовать ровный маршрут на карте?
Если просто соединить все точки по порядку, то имеем 2 проблемы:

1. Слишком много точек. Эта проблема решается с помощью алгоритмов симплификации кривой, например RDP.
2. GPS не идеален, и иногда ошибка может быть 100-200 метров. В итоге на карте появляются зигзаги, петли и прочие некрасивые вещи, хотя очевидно человек просто двигался по прямой.

Пример:


черное - если просто соединить точки по порядку
красное - примерно то, что требуется

Вопрос: может ли кто-то подсказать нужный алгоритм или хотя бы дать совет, куда копать? Интересует именно возможность сглаживания ошибок.

Comments

[Griboks]

хотя очевидно человек просто двигался по прямой

Очевидно, что вы ошибаетесь. Как вы ошибочно определяете, что точка неправильная? Вы ходите за пользователями с правильным GPS? Почему только GPS? Почему не используете другие геотрекеры?

[sim3x]

Griboks, Какие другие?

[Griboks]

sim3x, сотовые сети. Данные же по ним передаются на сервер. Глупо использовать вместо наивной геолокации оную от GPS.

[sim3x]

Griboks, А как получить такую геолокацию непривилегированному аппу/компании?

[Griboks]

sim3x, так же, как и GPS. Необходимо, что бы пользователь включил уточнение GPS через мобильные сети (и WiFi).

[Stalker_RED]

У точек есть привязка по времени? Может он действительно зашел не туда, а затем и вернулся. А может это отраженный сигнал gps дал такой скачек на пару секунд.
Две большие разницы ©.

[Satangelus]

Griboks, Сотовые сети, по мне это еще большая жесть. В гугл мапс как-то включил сохранение трека при определение позиции по данным сотовой сети. Не вязка была до 300 метров.

[xmoonlight]

Satangelus, Не согласен! Я лично кодил на питоне этот момент. Всё зависит от устройства и покрытия зоны сотовыми передатчиками.

[Griboks]

Satangelus, а я как-то включил, и точность была до метра. Это зависит от местности, станций, устройства и звёзд над головой. В любом случае, иметь 20 маяков лучше чем 10.

[Satangelus]

Griboks, согласен 20 маяков это классно. Но когда в районе 1-2 вышки (глубокая провинциальная глубинка, спальный район) провайдера считают, что больше будет слишком жирно. Тогда при определении позиции по вышкам выходит ерунда.

[Satangelus]

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

[Griboks]

Satangelus, в чистом поле или глубокой провинции gps работает без ошибок, ведь там нету высоких зданий.

[dom1n1k]

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

Answer 1

[pfg21]

взять гео-инфомационную систему типа Nexgis QGIS (бесплатная и программисты русскоговорящие) и пошарить в ее документации насчет сглаживания треков.
вообще алгоритмов усреднения/сглаживания последовательности - куча, только надо будет подобрать подходящий, выдающий наилучшую линию на основе тестового набора данных.

Answer 2

[Johny Smith]

https://en.wikipedia.org/wiki/Curve_fitting

Software
Many statistical packages such as R and numerical software such as the GNU Scientific Library, MLAB, Maple, MATLAB, GNU Octave, and SciPy include commands for doing curve fitting in a variety of scenarios. There are also programs specifically written to do curve fitting; they can be found in the lists of statistical and numerical analysis programs as well as in Category:Regression and curve fitting software.

Answer 3

[Влад]

Это не просто. И усложняется, если нужно сглаживание в реальном времени. Если нет — сглаживайте не текущее, а прошедшее (3-5 точек, в зависимости от скорости объекта).

1. Слишком много точек.

Больше измерений — меньше ошибок. А для лишнего можно применить фильтрацию и прореживание.

2. GPS не идеален...

Фильтр по скорости: строить радиус (или сектор) ожидания появление следующего отсчёта и отбрасывать, если в него не попадает.

Answer 4

[xmoonlight]

Скорость перемещения вектора отслеживайте и суммарный вектор перемещения относительно предыдущей опорной точки пути с глубиной 3-4 (направление перехода).

По рисунку: 2-е точки вблизи друг друга (4,6 и 7,8) - сразу понятно, что скорость там упала. Значит можно фиксировать опорную точку в этом радиусе и возможный излом траектории маршрута.

Соседние допуски - просчитываются на основании ускорения (засечек времени на координатах).

Для визуализации - используйте кривые Бизье. Это намного будет лучше для визуального восприятия и сильно упростит Вам понимание сглаживания трека маршрута.

Answer 5

[Moskus]

хотя очевидно человек просто двигался по прямой

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

Answer 6

[d'Ivan]

Поищи:

• "line simplification"
  
• "Douglas-Peucker algorithm"
  
• "FastSTray algorithm"
  

Answer 7

[boss_lexa]

https://developers.google.com/maps/documentation/r...