Полигональная оптимизация вывода точек треков перемещения объектов

Система Visitech «Мониторинг» предназначена для решения задач, связанных с мониторингом персонала и техники. Одна из важнейших — точное геопозионирование с заданной точностью вне и внутри зданий с выводом на карту информации о любых происходящих событиях.

Большое количество точек в треках перемещения объектов мониторинга может негативно сказываться на производительности системы и вызывать сложности с интерпретацией этих данных конечными пользователями. Всем привет, меня зовут Дмитрий Чернышов, работаю в команде Visitech, и сегодня я расскажу, как мы оптимизировали вывод треков объектов мониторинга.

Небольшой рассказ об особенностях Visitech и проблематике

Visitech получает данные о местонахождении объектов (сотрудники, транспортные средства, мобильное оборудование, грузы и т.д) с помощью трекингового оборудования различного типа. На типах оборудования сейчас не буду останавливаться — это весьма обширная тема. Благодаря трекинговым данным можно:

1. Понимать точное местонахождение отслеживаемых объектов с заданной точностью внутри и вне зданий.

2. Получить единую карту предприятия, на которой отображается информация о происходящих событиях: места, где планируются и уже проводятся работы, места, где происходят нарушения при проведении работ, и места, где потенциально может произойти опасная ситуация (сотрудник находится близко к опасной зоне, не соблюдает правила ношения СИЗ или правила безопасности при проведении работ).

3. Разграничить права доступа сотрудников. При помощи функции создания геозон карту объекта можно разметить на отдельные участки для обозначения всех функциональных зон объекта и дополнительно разграничить права доступа сотрудников в них, в том числе контролировать доступ сотрудников в опасные или запрещенные для посещения зоны, где проводятся работы повышенной опасности

4. Обеспечить контроль за техническим состоянием стационарных объектов и транспортных средств: при помощи интеграции с системами типа ТОРО\ТОиР и системами учета состояния транспортных средств Visitech понимает, где сотрудники не произвели обходы или не выполнили запланированные работы и ремонты.

5. Контролировать безопасность при проведении работ при помощи использования систем видеоаналитики, включая контроль за соблюдением регламентов по охране труда и промышленной безопасности: наличие СИЗ, предиктивная аналитика и выявление опасных условий и действий при проведении работ.

Итак, краеугольный камень — это построение треков передвижения. Чтобы не падала производительность, а результаты были легко интерпретируемыми, нам надо было оптимизировать вывод треков.

Мы проработали следующие методы:

• предварительная обработка треков на backend‑стороне системы;

• сжатие данных треков перемещения объектов при их выдаче на отрисовку на карте;

• кеширование данных;

• оптимизация отрисовки треков перемещения объектов на frontend‑стороне системы.

Рассматриваемые методы и алгоритмы оптимизации

Критерии выбора методов предварительной оптимизации

• Сочетание простоты и эффективности для обработки больших наборов данных

• Гарантированная точность — желательно иметь контроль над допустимыми отклонениями и уровнями точности

• Гибкость в применении

Рассматриваемые алгоритмы оптимизации

• Алгоритм Ланг‑Слоан

Основа: угловое изменение перед и после вершины трека.

Принцип выбора предела: заданный угловой порог.

Плюс: хорош для сохранения углов.

Минус: неэффективен для линий с плавными кривыми.

Вывод: нам не подходит.

• Алгоритм углового предела

Основа: углы между сегментами трека.

Принцип выбора предела: заданный угловой порог, ниже которого углы считаются незначительными и соответствующие точки удаляются.

Плюс: прост в реализации.

Минус: может не сохранять общую форму.

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

• Алгоритм Дугласа‑Пекера

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

Принцип выбора предела: заданный порог отклонения, основанный на допустимом максимальном расстоянии.

Плюс: хорошо сохраняет общую форму линии.

Минус: могут быть проблемы с невалидными данными (шумами).

Вывод: эффективен для длинных полигональных линий с большим количеством точек, где важна общая форма, а не мелкие детали.

• Алгоритм топологической упрощенности

Основа: топологические свойства точек трека (самопересечение, вложенность, …).

Принцип выбора предела: избегание самопересечений, сохранение топологической целостности.

Плюс: поддерживает топологические особенности.

Минус: сложен в реализации.

Вывод: нам не подходит.

• Алгоритм радиального расстояния

Основа: расстояние точек трека от начальной до каждой последующей.

Принцип выбора предела: заданный радиальный порог, который определяет, какие точки можно сохранить.

Плюс: прост в реализации.

Минус: может не сохранять мелкие детали формы.

Вывод: подходит для линий, где точки распределены равномерно вокруг центральной линии и важно сохранить радиальные характеристики.

• Алгоритм Ритмана‑Викера

Основа: изменение длины и площади трека при удалении точки.

Принцип выбора предела: заданный порог «важности» точки, измеряемый изменением длины и площади трека.

Плюс: хороший компромисс между формой и упрощением.

Минус: требует предобработки перед оптимизацией.

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

Исследование и разработка

Используемый датасет: набор данных GPS‑траекторий проекта Geolife (Microsoft Research Asia), скачать.

Далее рассмотрим только те алгоритмы, которые не отмели сразу (углового эталона, радиального расстояния, Дугласа-Пекера, Реймана-Виткама).

Угловой эталон

• Трек упрощается путем удаления вершин, основываясь на величине угла между соседними сегментами.

• Если угол между двумя соседними сегментами меньше заданного порогового значения, вершина между этими сегментами удаляется.

• Процесс продолжается до тех пор, пока не будут удалены все вершины, угол которых меньше порогового значения.

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

Радиальное расстояние

• Для каждых из двух точек проверяется превышение суммой квадратов расстояний допустимого отклонения.

• Если квадрат расстояний меньше допустимого отклонения точка из маршрута удаляется.

Результат: алгоритм схож с алгоритмом Дугласа‑Пекера, но плохо работает с фильтрацией ошибочных выбросов координат, когда точка маршрута резко перемещается на достаточное удаление и потом также резко возвращается на реальную траекторию движения. Поэтому мы отказались от его применения.

Дуглас-Пекер

• Выбор начальной и конечной точек трека.

• Определение точки, которая находится на максимальном расстоянии от прямой, соединяющей начальную и конечную точки.

• Если это расстояние меньше заданного порога, все точки между начальной и конечной удаляются.

• Процесс продолжается до тех пор, пока все точки, кроме начальной и конечной, не будут проверены.

Результат: алгоритм соответствует ожиданиям.

Рейман-Виткам

• Выбор начальной и конечной точек трека.

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

• Если это максимальное расстояние превышает заданный порог, точка с наибольшим расстоянием сохраняется, и процесс повторяется для сегментов, образованных этой точкой.

• Если расстояние меньше порога, промежуточные точки удаляются.

Результат: алгоритм соответствует ожиданиям.

Дополнительная обработка

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

• Разрежение трека: удаление точек, расстояние между которыми меньше 2 метров.

• Удаление выбросов из трека: выявление аномалий, где угол между самыми длинными векторами, исходящими из точки, и среднее расстояние между точками для данных векторов больше 10 метров.

• Выравнивание треков к средней скорости: удаление точек с резко изменяющейся скоростью (более 13 м/с).

• Оптимизация остановок: если точка находится в пределах допустимого расстояния от центра кластера (100 метров) и продолжительность нахождения в кластере превышает минимальное значение (около 20 минут) — замена на среднюю координату кластера.

Итоговое сравнение и результаты

Методы оптимизации Дугласа‑Пекера и Реймана‑Виткама являются наиболее оптимальными методами при работе с треками передвижения объектов мониторинга. Они позволяют эффективно сокращать количество точек и сохранять важные характеристики маршрута движения.

• Алгоритм Дугласа‑Пекера является оптимальным для длинных полигональных линий с большим количеством точек. В маршрутах передвижения объектов мониторинга важно сохранить общую форму маршрута, однако на тестовых треках качество сжатия трека сравнительно с алгоритмом Реймана‑Виткама меньше в среднем на 30%.

• Алгоритм Реймана‑Виткама отлично подходит для линий с большим количеством точек, где важно сохранить основные характеристики и удалить менее значимые точки. В контексте маршрутов передвижения объектов мониторинга это означает, что можно эффективно удалить лишние точки, которые не играют ключевой роли в маршруте, сохраняя при этом важные точки и характеристики.

• Выбор конкретной реализации оптимизационного алгоритма определяется по средней медианной длине трека. Соответственно система автоматически выбирает оптимальный алгоритм, что позволяет работать с разнообразными треками и не упираться в ограничения каждого из них.

Спасибо за внимание, если есть вопросы по теме — буду рад ответить!