Как уменьшить набор баллов?
У меня есть упорядоченный список точек (широта, долгота) на маршруте. У меня есть упорядоченный список остановок (лат, лонг). Допустим, у меня 1000 очков и 20 остановок. Я хотел бы уменьшить 1000 баллов до примерно 100 в зависимости от того, какие баллы более актуальны для маршрута. Например, точки, которые вызывают повороты.
Один из способов, как я думаю, что я могу это сделать, - это группироваться вокруг остановок и выбирать точки, может быть, наугад Но это все еще не кажется эффективным для меня. Я уже использую алгоритм Дугласа Пекера. Помимо этих каких-либо идей?
1 ответ
Вы можете использовать алгоритм Рамера-Дугласа-Пекера, чтобы упростить вашу ломаную линию.
Для исходной комплексной полилинии этот алгоритм получает новую полилинию, аппроксимирующую оригинал с заданной погрешностью e, Точки, определяющие новую полилинию, являются подмножеством оригинала.
Алгоритм является пошаговым, начиная с конечных точек полилинии и добавляя точку, наиболее удаленную от текущего приближения, на каждой итерации. Алгоритм сходится, когда все остальные точки находятся в пределах перпендикулярного расстояния e текущего приближения.
Алгоритм основан на подходе типа "разделяй и властвуй" и, следовательно, имеет ожидаемую сложность: O(n*log(n)) (хотя наихудший случай O(n^2)).
Из-за поведения "наихудший - первый" полученная полилиния включает в себя "важные" точки, которые определяют острые углы, при этом исключая псевдо-избыточные точки вдоль плоских участков в пределах допуска e,