304
правки
Изменения
Нет описания правки
Упрощение полигональной цепи - процесс, позволяющий уменьшить число точек кривой, аппроксимированной серией точек.
==Задача==
Пусть у нас есть некоторая аппроксимированная кривая, все точки которой нам не нужны, а большинство из них лишь занимает место. Такое встречается при обработки векторной графики и построении карт. Расмотрим пример для построения карт. Пусть у нас есть путь из Москвы в Санкт-Петербург, заданный точками через каждый километр пути. В маштабах всей России такая точность явно ни к чему, стоит оставить лишь точки, отражающие ключевые участки пути. В этом случае нам и пригодится упрощение, одним из вариантов реализации которого является алгоритм Дугласа-ПекераДугласа—Пекера.
==Алгоритм Дугласа-Пекера==
Суть алгоритма Дугласа-Пекера(Douglas–PeuckerDouglas-Peucker) состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
===Описание===
Начальная кривая представляет собой упорядоченный набор точек.
При определении расстояния от точки до отрезка нужно сначала проанализировать взаимное расположение точки и отрезка прямой, то есть, проверить, куда опустится перпендикуляр из точки: непосредственно на отрезок или на прямую, являющуюся продолжением рассматриваемого отрезка. Если на отрезок, то ответ это расстояние от исходной точки до точки пересечения отрезка с перпендикуляром, если нет, то расстояние от исходной точки до одного из концов отрезка. Первое, что приходит в голову, это найти точку пересечения перпендикуляра и прямой, и в зависимости от ее положения вычислить ответ. На самом деле этот анализ может быть произведен путем построения треугольника, вершинами которого являются концы отрезка и точка, и сопоставления соотношения длин его сторон.
===Реализация===
[[Файл:DistancePointToSegment.gif|300px|right]]
Пусть даны точка <tex>(x_0; y_0)</tex> и отрезок, заданный точками <tex>(x_1; y_1)</tex> и <tex>(x_2; y_2)</tex>.
Тогда обозначим за <tex>R_1</tex> расстояние от <tex>(x_0; y_0)</tex> до <tex>(x_1; y_1)</tex>,
за <tex>R_2</tex> расстояние от <tex>(x_0; y_0)</tex> до <tex>(x_2; y_2)</tex> и
за <tex>R_{12}</tex> расстояние от <tex>(x_1; y_1)</tex> до <tex>(x_2; y_2)</tex>.
Если <tex>R_1 \ge \sqrt{R_2^2+R_{12}^2}</tex>, то ответ это <tex>R_2</tex>.
Если <tex>R_2 \ge \sqrt{R_1^2+R_{12}^2}</tex>, то ответ это <tex>R_1</tex>.
Если оба условия ложны, то ответ это расстояние от точки до продолжения отрезка до прямой, который выражается как модуль <tex>|R_{12} * R_1|/|R_{12}|</tex>, где <tex>R_{12}</tex> и <tex>R_1</tex> нужно рассматривать как вектора, а умножение как векторное произведение.
==Ссылки==
[http://ru.wikipedia.org/wiki/Алгоритм_Рамера_—_Дугласа_—_Пекера Алгоритм Дугласа — Пекера]
[http://pers.narod.ru/algorithms/pas_dist_from_point_to_line.html Поиск расстояния от точки до отрезка]
[http://algolist.manual.ru/maths/geom/distance/pointline.php Поиск расстояния от точки до прямой]
