рації надходять даних.
Мета даної роботи - розробити простий блочно-часовий алгоритм фільтрації геолокаційні даних, який дозволяє зберігати додаткові характерні точки, такі як:
" Точки простою" спостережуваного об'єкта,
" Контрольні точки" по відстані і часу.
Таким чином, пропонується спочатку виділити на треку" точки простою" і" контрольні точки" і використовувати їх як точки розбиття вихідної ламаної на подломание, до кожної з яких вже застосовувати класичні алгоритми спрощення ламаних, наприклад, алгоритм Рамера - Дугласа - Пекера.
Алгоритм виділення" точок простою"
" Точка простою" характеризується тим, що протягом деякого проміжку часу, не менше т, всі координати потрапили в коло радіуса S, а все більш ранні і більш пізні точки лежать на відстані не менше S2 від цієї окружності. Всю групу точок, що потрапила в цю окружність, ми будемо замінювати не однієї, а двома точками: самій ранній і самої пізньої. Таким чином, ми збережемо інформацію про час прибуття спостережуваного об'єкта на стоянку і часу виїзду зі стоянки. Якщо ж дана група точок за часом потрапляє в діапазон т, ми замінимо дану групу точок не двома, а однією. Таким чином, окрім виділення" точок простою" дана частина алгоритму буде додатково фільтрувати вхідні дані за принципом" найближчий сусід".
На вхід алгоритму надходять геолокаційні дані, які накопичуються в буфері parking, поки радіус околиці, описаної навколо точок цього буфера, не перевищує?.
for point in input_stream:
Якщо всі крапки поміщаються в потрібному околиця - нехай поміщаються if circle (parking + point). Radius < delta:
parking.append (point)
якщо ж нова точка не лізе, пора закінчувати else:
# Якщо пройшло більше tau - то це стоянка, додаємо першу і останню if parking.last - parking.first.time> tau: output.append (parking.first) output.append (parking.last) else: # час невелике, стискаємо крайні точки в одну «середню»
midpoint=(parking.last + parking.first) / 2 output.append (midpoint)
очищаємо парковку parking=[]
і точку, яка не влізла в попередню парковку, кладемо в нову parking.append (point)
Якщо використовувати ефективний алгоритм знаходження радіуса описаного кола, наприклад [3], має складність O (n), то в гіршому випадку складність пропонованого алгоритму буде O (n2).
Недоліком даного алгоритму є можливість розростання тимчасового буфера parking, наприклад у випадку, якщо відстежується об'єкт занадто довго перебуває на стоянці. Однак і цей недолік легко усувається - досить лише додавати в parking тільки ті точки, які призводять до зростання околиці.
Якщо пожертвувати точністю і замість окружності використовувати прямокутну околиця, алгоритм, очевидно, матиме складність O (n).
Реалізація та апробація результатів
Алгоритм був реалізований на мові Python і використовується в складі програмного комплексу 'Хто куди" (ТОВ" Лаб М" ) для фільтрації геолокаційні даних від апаратних GPS / ГЛОНАСС-трекерів, встановлених на автомобілях, що пересуваються по м. Самара і області і передавальних годинне в середньому 10 разів на хвилину.
Дані надходили у фільтр, що виділяє" точки простою", з виходу цього фільтра - в проміжний буфер. До даних в проміжному буфері застосовувався алгоритм Рамера - Дугласа - Пекера, для блоку даних між" точками прост...
