Предисловие
Недавно на работе задали задачу — есть клиент с GPS устройством. Ходит, он значит по городу и записывает на это устройство каждую секунду координату своего местонахождения. Потом заходит на наш сайт и отправляет файл с записями маршрута. И в ответ получает изображение карты и поверх нарисованный маршрут по которому он двигался. Все вроде бы ничего, но есть одна проблемка — клиент может записывать хоть целый день и прислать громадный файл, а отрисовка маршрута занимает очень много времени. А он ведь мог идти по прямой линии и тогда смысл отрисовывать все точки отпадает(ценных только две крайних). Тем более рисуется она на JavaScript на клиентской стороне и если клиентская сторона это мобильное устройство вполне вероятно что маршрут он не увидит((
И потому мне надо было сделать небольшую оптимизацию — оптимально упростить ломанную линию. Для этой задачи существует метод Дугласа-Пекера, но на русском описания этого метода я не нашёл, поэтому я решил заполнить этот пробел рунета.
Алгоритм
Сразу привожу ссылку(англ) на статью по которой я разбирался.
Картинки тоже от туда.
Итак, мы имеем список точек {V} и заданное максимально-допустимое отклонение (е).
1) Рассматриваем сначала всю ломаную
1.1) Ищем точку которая максимально отдалённая от линии [V0,Vn] (на рисунке [V0,V7])
1.2) Проверяем — если расстояние от этой точки(на рисунке V3) до линии [V0,Vn] меньше чем (е), то все точки на сегменте (V0,Vn) можно выбрасывать.
1.3) В противном случае мы разбиваем рассматриваемый сегмент на 2 части(на рисунке (V0,V3) и (V0,V7)).
2) Дальше все рекурсивно повторяется. Отдельно рассматриваем сегменты (V0,V3) и (V0,V7). На каждом из них находим точку которая максимально отклоняется от главного направления на сегменте. Проверяем, если эта точка отклоняется не больше чем на (е), то все точки на сегменте вбрасываем. Иначе, данный сегмент разбивается на 2 и рекурсивные вызовы функции повторяются.
Ниже приведённая иллюстрация, заполнит все оставшиеся пробелы в понимании алгоритма которые могли остаться у читателя.
Реализация
Я алгоритм писал на Java. Кого интересует вариант для С++ следуйте сюда, или Паскаль — туда.
public class DouglasPoikerSimplification {
private static double tolerant; // максимально-допустимое отклонение (е)
private static Point[] polyline; // список точек
private static ArrayList<Integer> markedPoints; // список новых точек (результирующая ломаная)
public static Point[] getSimplificatedPolyline(Point[] plots, double tolerant){//tolerant = 0.00005
DouglasPoikerSimplification.tolerant = tolerant;
DouglasPoikerSimplification.polyline = plots;
DouglasPoikerSimplification.markedPoints = new ArrayList<Integer>();
markedPoints.add(0);
simplify(0, plots.length-1); // разссмотрим всю ломаную
markedPoints.add(polyline.length-1);
return writePointArray();
}
private static Point[] writePointArray(){
Integer[] idx = new Integer[markedPoints.size()];
idx = markedPoints.toArray(idx);
Arrays.sort(idx);
Point[] result = new Point[idx.length];
for (int i = 0; i < result.length; i++) {
result[i] = polyline[idx[i]];
}
return result;
}
private static void simplify(int j, int k){
if(k == j+1){ // если в сегменте нет промежуточных точет, а только две крайние
return; // то выйти
}else{
double maxd = -1; // максимальная удалённость точки от основного направления в сегменте
int maxi = j; // индекс точки которая максимально отдалённая от осн. напр. в сегменте
for (int i = j+1; i < k; i++) { // перебираем промежуточные точки в сегменте
// вычисляем дистанцию от точки до основной линии в сегменте
double dv = Point.getDistance(polyline[j], polyline[k], polyline[i]);
if(dv > maxd){// если оно больше всех предыдущих, то
maxi = i; // запоминаем индекс этой точки
maxd = dv; // и её растояние к отрезку основ. направления в сегменте
}
}
if(maxd > tolerant ){// если максимальное отклонение больше допустимого, то
markedPoints.add(maxi); // заносим эту точку в результирующий список
// System.out.println(polyline[maxi].getLat() + "\t\t " + polyline[maxi].getLng());
simplify(j, maxi);// и делаем всё тоже для двух полученых сегментов
simplify(maxi, k);
}
}
}
}
Результат
Отклонение я взял 0.00005 это приблизительно 5.5 метров. Файлы присланные на сайт были средние от 1Мб до 1.5Мб.
before after before/after
65529 3535 18.5371994342291
56996 4131 13.7971435487775
41198 4699 8.76739731857842
35166 2408 14.6038205980066
34906 1437 24.2908837856646
average 15.9992889370513
Видим что в среднем количество точек уменьшилось в 16 раз.
