Как уменьшить количество точек?

Question

У меня есть упорядоченный список точек (lat, long) по маршруту. У меня есть упорядоченный список остановок (lat, long). Скажем, у меня 1000 очков и 20 остановок. Я хотел бы уменьшить 1000 пунктов до примерно 100, в зависимости от того, какие точки больше подходят для маршрута. Как и точки, которые индуцируют повороты, например.

Один из способов, я думаю, могу сделать это, чтобы сгруппировать вокруг стопов и выбирать точки, возможно, в случайном порядке. Но это все еще кажется мне неэффективным. Я уже использую алгоритм Дугласа Пиккера. Помимо этих идей?

Answer 1

Вы можете использовать алгоритм Ramer–Douglas–Peucker для упрощения вашей полилинии.

При заданной исходной комплексной полилинии этот алгоритм получает новую полилинию, аппроксимирующую оригинал с заданным допуском погрешности e. Точки, определяющие новую полилинию, являются подмножеством оригинала.

Алгоритм является инкрементным, начиная с конечных точек полилинии и добавляя точку, наиболее удаленную от текущего приближения на каждой итерации. Алгоритм сходится, когда все остальные точки находятся в перпендикулярном расстоянии e текущего приближения.

Алгоритм основан на подходе типа «divide & conquer» и, следовательно, имеет ожидаемую сложность O(n*log(n)) (хотя наихудший вариант - O(n^2)).

Из-за его «худшего первого» поведения получившаяся полилиния включает в себя «важные» точки, которые определяют острые углы, исключая псевдо-избыточные точки вдоль плоских участков в пределах допуска e.