304
правки
Изменения
→Мотивация
Дана некоторая аппроксимированная кривая, заданная последовательностью точек, и некоторое <tex>\varepsilon</tex>. Требуется ответить, какие точки мы можем оставить, так чтобы расхождение между исходной и получившейся кривыми не превышало <tex>\varepsilon</tex>, при этом количество точек в получившейся кривой должно стремиться к минимуму.
==Мотивация==
Такая задача встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть Дан путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-Пекера.
==Алгоритм Дугласа-Пекера==
