Имеются ли какие алгоритмы оптимизации точек на карте?

Question

[Максим Гречушников]

Есть gpx данные по точкам. нужно построить маршруты.
нужно каким то образом определить необходимые вершины, и удалить лишние точки. Какие существуют для этого алгоритмы?

нашел вот такое. https://en.wikipedia.org/wiki/Ramer–Douglas–Peucke...
возможно можете что то еще интересного подсказать

Comments

[Алан Гибизов]

Если нет кода, не надо ставить тэг языка.

Answer 1

[hint000]

нашел вот такое ...

Простым хождением по ссылкам с этой же найденной вами страницы можно в два-три клика (буквально) найти больше:
https://en.wikipedia.org/wiki/Cartographic_general...

Comparison of several common line generalization algorithms. Gray: original line (394 vertices), orange: 1973 Douglas-Peucker simplification (11 vertices), blue: 2002 PAEK smoothing (483 vertices), red: 2004 Zhou-Jones simplification (31 vertices). All were run with the same tolerance parameters.

https://en.wikipedia.org/wiki/Visvalingam–Whyatt_a...
https://en.wikipedia.org/wiki/Smoothing (в сводной таблице сравниваются аж 17 разных алгоритмов)

А ещё, когда говорим о любой оптимизации чего угодно, нужно в первую очередь сформулировать критерий оптимальности, иначе разговор потеряет смысл с математической/алгоритмической точки зрения. Т.е. нужно формальное определение цели, к которой стремимся. Например, цель - максимальная простота алгоритма и уменьшение количества точек в N раз. Очевидный алгоритм, достигающий этой цели - оставить каждуую N-ную точку по порядку, остальные удалить. Можно только догадываться, что такой вариант вам не интересен, но для выбора конкретного алгоритма цель должна быть сформулирована конкретно.

Answer 2

[Сергей П]

А что тут вообще сложного? Просто находите точки, угол между ребрами в которых ближе всего к 180 градусов. Их можно удалять. Угол между векторами считается просто, легко погуглить.
Еще можно отправить ключевые точки в Построитель маршрута типа osrm и он выдаст красивую геометрию маршрута по дорогам.