304
правки
Изменения
→Задача
Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которой которого является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
