Н.В. Бейліна
Постановка завдання
Геолокаційні дані, що описують переміщення спостережуваного об'єкта, являють собою послідовність кортежів виду (lon, lat, time, ...), де lon, lat - географічні координати об'єкта (широта і довгота), time - час отримання координати, а трьома крапками позначені додаткові дані , такі як висота над рівнем моря, миттєва швидкість і так далі.
Геолокаційні дані, що надходять в інформаційні системи від датчиків GPS / ГЛОНАСС, найчастіше надлишкові: наприклад, багато датчики передають координати один раз в секунду, тоді як для реального застосування достатньо даних з точністю до хвилини, а іноді істотно рідше.
Припустимо, що в інформаційну систему передаються лише широта, довгота, штамп часу (по 64 біта), висота над рівнем моря і швидкість (по 16 біт). Без урахування накладних витрат кожен запис має розмір 28 байт. Однак, якщо дані надходять раз в секунду, за добу від одного спостережуваного об'єкта в систему надійде близько 2,3 МБайт даних, 840 Мбайт на рік. Зрозуміло, що побудова різних аналітичних звітів за такими обсягами може бути важко для невеликих організацій, що не володіють обладнанням з відповідною обчислювальною потужністю.
З урахуванням того, що інформація, за емпіричними підрахунками, надлишкова приблизно в 60 разів, досить актуальним є питання фільтрації надходять в інформаційну систему даних, по можливості здійснюваний одночасно з прийомом даної інформації або з невеликою затримкою, але невеликими блоками.
Очевидно, що (lon, lat), розташовані в порядку зростання часу, являють собою вершини ламаної. Для спрощення ламаних ліній часто використовується алгоритм Рамера - Дугласа - Пекера [1; 2]. Він відрізняється простотою реалізації, високою ефективністю, а його складність оцінюється як O (n2). Саме цей алгоритм використовується в більшості геоінформаційних систем для відображення кінцевому користувачеві траєкторії руху об'єкта, що спостерігається на карті.
Формально алгоритм Рамера - Дугласа - Пекера можна застосувати до будь-якої ламаної, тобто до будь-якої частини наявних даних. Алгоритм зберігає т. н. '' Характерні" точки ламаної, видаляючи з неї ті, що лежать на відстані, що не перевищує? від прямої, що з'єднує інші точки. Однак серед цих точок можуть виявитися також і точки, несучі додаткове смислове навантаження, наприклад, точки тривалого простою спостережуваного об'єкта або проміжні точки на довгих прямолінійних ділянках магістралей - вони є зайвими з точки зору алгоритму Рамера - Дугласа - Пекера, але можуть бути важливим елементом для інших бізнес-процесів підприємства, що експлуатує інформаційну систему.
Типовими 'втратами" при застосуванні алгоритму Рамера - Дугласа - Пекера (і багатьох інших алгоритмів спрощення ламаних) до даних геолокації є:
втрата місць 'простою" спостережуваного об'єкта, коли стає неможливо визначити, як довго насправді знаходився об'єкт в околиці деякої точки;
втрата проміжних точок спостережуваного об'єкта при його русі за прямолінійним шосе.
Це пов'язано з тим, що алгоритм Рамера - Дугласа - Пекера враховує лише відстані (у простому випадку - на площині), але не враховує час.
Крім того, багато алгоритми спрощення ламаних, і зокрема алгоритм Рамера - Дугласа - Пекера, не є поточними, тобто вимагають наявності всіх вхідних даних відразу, в даному випадку - всієї ламаної, тоді як є необхідність у блочно-потокової фільт...
