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