Задать вопрос
@Stalinko
PHP'шник и фрилансер до мозга костей
алгоритмы

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

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

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

Пример:
5b5f180d110c5849571407.png

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

Вопрос: может ли кто-то подсказать нужный алгоритм или хотя бы дать совет, куда копать? Интересует именно возможность сглаживания ошибок.
  • Вопрос задан
  • 2247 просмотров
13 комментариев
Подписаться 10 Средний 13 комментариев
Пригласить эксперта
Ответы на вопрос 7
@pfg21
ex-турист
взять гео-инфомационную систему типа Nexgis QGIS (бесплатная и программисты русскоговорящие) и пошарить в ее документации насчет сглаживания треков.
вообще алгоритмов усреднения/сглаживания последовательности - куча, только надо будет подобрать подходящий, выдающий наилучшую линию на основе тестового набора данных.
Ответ написан
Комментировать
Комментировать
Olek1
@Olek1
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.
Ответ написан
Комментировать
Комментировать
@vlad_bo
3D modeler
Это не просто. И усложняется, если нужно сглаживание в реальном времени. Если нет — сглаживайте не текущее, а прошедшее (3-5 точек, в зависимости от скорости объекта).
1. Слишком много точек.

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

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

Фильтр по скорости: строить радиус (или сектор) ожидания появление следующего отсчёта и отбрасывать, если в него не попадает.
Ответ написан
Комментировать
Комментировать
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Скорость перемещения вектора отслеживайте и суммарный вектор перемещения относительно предыдущей опорной точки пути с глубиной 3-4 (направление перехода).

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

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

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

Из чего очевидно? В общем случае, это совершенно не очевидно, если нет каких-то дополнительных ограничений, например - что пользователь гарантированно двигался на автомобиле по улице. Если никаких подобных ограничений нет, то любое "причесывание" будет необоснованной фантазией.
К трекам, конечно, можно применять кое-какие средства оптимизации. Например, убирать сегменты, где скорость нетипично высока (которые могут быть выбросами из-за плохого приема). Но простого алгоритма причесывания треков просто не может быть.
Ответ написан
Комментировать
Комментировать
2ord
@2ord
Поищи:
  • "line simplification"
  • "Douglas-Peucker algorithm"
  • "FastSTray algorithm"
Ответ написан
Комментировать
Комментировать
@boss_lexa
https://developers.google.com/maps/documentation/r...
Ответ написан
Комментировать
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Бэкенд программист
Grade Factor • Москва
от 80 000 ₽
С++ developer
TQB - хай-тек рекрутмент по-хардкору • Москва
от 300 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Исправление ошибок в работе вебсайта / Доработка интернет-магазина
24 апр. 2024, в 02:51
50000 руб./за проект
Анимация логотипа
24 апр. 2024, в 00:08
20000 руб./за проект
Разработка дизайна раздела «Статьи» на сайте «Мир отходов»
23 апр. 2024, в 23:01
10000 руб./за проект
Ещё заказы