Изменения
Нет описания правки
Упрощение полигональной цепи {{---}} процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точекполилинии.
==Задача==
Дана некоторая аппроксимированная криваяполилиния, заданная последовательностью точек<tex> a_1, a_2, ..., a_n</tex>, и некоторое <tex>\varepsilon</tex>. Требуется ответитьнайти цепь <tex> a_1, какие точки мы можем оставитьa_i, так чтобы расхождение между исходной и получившейся кривыми не превышало a_j, ..., a_n </tex>, для которой верно, что для <tex>k</tex>, такого что<tex> i < k < j:</tex> <tex>distance(a_k,\overrightarrow{a_i a_j}) \le \varepsilon</tex>, при этом количество точек в получившейся кривой должно стремиться к минимумудля любых соседних <tex>i</tex> и <tex>j</tex>.
Существует также альтернативная задача, в которой вместо <tex>\varepsilon</tex> задано число <tex>k</tex> вершин в итоговой цепи.
