Алгоритм Дугласа-Пекера

[pallada92]

Спасибо за статью! Периодически приходится решать подобные задачи отбражении карт в d3.js или WebGL, когда topoJSON файл границ регионов нужно сконверировать в набор полигонов с разумным числом точек и заанимировать. Мне было достаточно простого алгоритма, который пропускает точки, которые находятся слишком близко друг другу и дробит длинные отрезки. Не думал, что существует семейство алгоритмов для решения этой задачи с более точными гарантиями.
Если не секрет, для какой именно задачи вам потребовалась упрощать цепи?

[VladimirBalun]

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

[little-brother]

Конкретно для графиков неплох Largest Triangle Three Buckets от Sveinn Steinarsson. К тому же для популярных языков уже имеется реализация.

[VladimirBalun]

Спасибо, действительно очень неплох, буду иметь в виду.

[SaNNy32]

Было бы неплохо описать работу алгоритма при задании ограничения по количеству оставшихся точек после упрощения

[VladimirBalun]

Да, что-то я об этом совсем не подумал…
Постараюсь добавить это в статью в скором времени.

[Alexufo]

Тут выше уже упомянули Largest Triangle Three Buckets
Здесь я писал о варианте для одномерного массива.
habr.com/en/post/412629

[Dmirry]

Огромное спасибо! Понятно, лаконично, наглядно. Жду продолжения.

[freeExec]

А можно пример где нарушается топология и происходит пересечение.

[VladimirBalun]

Когда буду добавлять в статью правки по комментарию SaNNy32:

Было бы неплохо описать работу алгоритма при задании ограничения по количеству оставшихся точек после упрощения

Тогда заодно сделаю пример и визуализацию, где нарушается топология и происходят пересечения.