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