Как создать мастер-трек из большого набора координат, полученных от gps-трекеров?
Есть самописная система мониторинга транспорта.
Есть несколько сотен автомобилей, оснащенных gps-трекерами.
Все автомобили катаются из Москвы в регионы. Представьте карту Москвы и области, основные трассы, выходящие с МКАДа и идущие во Владимир, Екатеринбург, Красноярск, Питер, Краснодар и т.д. Десятки и сотни городов.
За год работы в системе накопилось несколько десятков миллионов координат. Если отобразить их на карте, то они в основном лягут на трассы, о которых говорилось выше. Иногда будет "мусорные координаты" - машина под крышей заправки, либо еще какие-то помехи, объез пробок. Например, в Питер из москвы можно ехать через Чехов. Узнали об этом только после запуска мониторинга. "Мусора" хватает.
Задача в следующем: научить систему мониторинга самостоятельно определять сход с основного/обычного маршрута движения. Для этого хочется все существующие точки обработать и получить т.н. мастер-трек. А потом искать ближайшую координату из мастер-трека к получаемой от трекера из машины, и если расстояние больше определенного 2 раза подряд, считать это сходом с маршрута.
Сейчас координаты хранятся в виде XX.XXXXXX и YY.YYYYYY. Т.е. точность шесть знаков после запятой. Мастер-трек должен содержать пять знаков после запятой.
Алгоритм должен отсеивать "мусор", т.е. если вокруг точки, которую мы рассматриваем в радиусе пяти знаков после запятой нет других точек или их меньше определенного количества, то мы считаем точку мусором и не учитываем в расчетах.
Т.е. начать можно с простого обрубания шестого знака после запятой. Потом "убираем" мусорные точки. А далее из оставшихся надо посчитать мастер-трек.
Много вариантов перепробовал и понял, что идеальный вариант - медиана. Но как ее применить к координатам, не знаю.
Коллеги, есть идеи?
Подумайте над таким вариантом:
1) руками на карте грубо рисуете геометрию области (не обязательно прямоугольную), где фигурирует четко один трек (чтобы выделить массив точек, относящихся к одному треку). Врядли это просто сделать автоматически
2) бьете всю обозначенную вручную область на небольшие квадраты. Для каждого из таких квадратов будем искать среднее значение. Вот как раз тут и можно учесть тот самый шестой знак - т.е. построить квадраты так, чтобы в координатах границ квадрата шестой знак был равен нулю (т.е. на каждый квадрат будет 10 возможных значений реальной координаты).
3) для каждого квадрата делаем выборку координат из базы (если есть нормальный пространственный индекс, должно быть быстро). Если в квадрат не попала ни одна координата, пропускаем его (таких будет большинство, но их будет тем меньше, чем точнее вы вручную выделили область одного трека). Если попала хотя бы одна (а лучше несколько) - считаем среднее значение. Это среднее значение становится частью мастер-трека.
Меняя размер вышеописанной "сетки" усреднения, можно либо уменьшать количество точек в мастер-треке, огрубляя определение схода с маршрута, либо увеличивать количество точек, также как и точность определения.
Спасибо за предложение! Я примерно с такого варианта и начинал. Брал все точки из базы и вокруг каждой рисовал квадрат или круг(считается дольше на mysql). Т.е. беру первую и "рисую" квадрат. Выбираю количество точек в квадрате. Потом количество точек в квадрате каждой их этих точек. Точку с максимальным количеством оставляю, а остальные точки из ее квадрата удаляю, чтобы не мешались. Потом беру другую точку и опять квардат и все по новой. В итоге оставался мастер-трек. Но колхозное решение. Хочется красиво с математикой сделать.
paralet вам шашечки или ехать?)) Не вижу никаких проблем с математикой. Могу посоветовать учитывать дисперсию и выкидывать точки, которые сильно отклоняются от среднего значения. Это называется методом наименьших квадратов: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D... . Вот будет вам математика (в принципе так и нужно делать в общем случае, вопрос - надо ли это вам, т.к. непонятно, насколько сильные у вас могут быть отклонения).
Мое мнение:
1) Думаю Можно сократить данные если, к примеру отсеять ближайшие/одинаковые точки при помощи кластеризации.
2)Численные Методы . Интерполяция.
Средний
