Comments 10
Спасибо за статью! Периодически приходится решать подобные задачи отбражении карт в d3.js или WebGL, когда topoJSON файл границ регионов нужно сконверировать в набор полигонов с разумным числом точек и заанимировать. Мне было достаточно простого алгоритма, который пропускает точки, которые находятся слишком близко друг другу и дробит длинные отрезки. Не думал, что существует семейство алгоритмов для решения этой задачи с более точными гарантиями.
Если не секрет, для какой именно задачи вам потребовалась упрощать цепи?
Если не секрет, для какой именно задачи вам потребовалась упрощать цепи?
Конкретно для графиков неплох Largest Triangle Three Buckets от Sveinn Steinarsson. К тому же для популярных языков уже имеется реализация.
Было бы неплохо описать работу алгоритма при задании ограничения по количеству оставшихся точек после упрощения
Тут выше уже упомянули Largest Triangle Three Buckets
Здесь я писал о варианте для одномерного массива.
habr.com/en/post/412629
Здесь я писал о варианте для одномерного массива.
habr.com/en/post/412629
Огромное спасибо! Понятно, лаконично, наглядно. Жду продолжения.
А можно пример где нарушается топология и происходит пересечение.
Когда буду добавлять в статью правки по комментарию SaNNy32:
Было бы неплохо описать работу алгоритма при задании ограничения по количеству оставшихся точек после упрощенияТогда заодно сделаю пример и визуализацию, где нарушается топология и происходят пересечения.
Sign up to leave a comment.
Алгоритм Дугласа-Пекера