Алгоритм Рамера

Алгоритм Дугласа-Пекера — это алгоритм, позволяющий уменьшить число точек кривой, аппроксимированной большей серией точек. Алгоритм был независимо открыт Урсом Рамером в 1972 и Давидом Дугласом и Томасом Пекером в 1973. Также алгоритм известен под следующими именами: Алгоритм Рамера-Дугласа-Пекера, алгоритм итеративной ближайшей точки и алгоритм разбиения и слияния.

Идея

Суть алгоритма состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.

Алгоритм

Сглаживание кусочно-линейной кривой алгоритмом Дугласа-Пекера.

Начальная кривая представляет собой упорядоченный набор точек или линий на расстоянии ε > 0. Начальная кривая показана на рисунке 0, упрощённая — на рисунке 4.

Алгоритм рекурсивно делит линию. Входом алгоритма служат координаты всех точек между первой и последней. Первая и последняя точка сохраняются неизменными. После чего алгоритм находит точку, наиболее удалённую от прямой, проведённой через первую и последнюю. Если точка находится на расстоянии, меньше чем ε, то все точки, которые ещё не были отмечены к сохранению, могут быть выброшены из набора и получившаяся прямая сглаживает кривую с точностью не ниже ε

Если же расстояние больше ε, то алгоритм рекурсивно вызывает себя с на наборе от начальной до данной и от данной до конечной точках (что означает, что данная точка будет отмечена к сохранению).

По окончанию всех рекурсивных вызовов выходная ломаная строится только из тех точек, что были отмечены к сохранению.

Псевдокод

function DouglasPeucker(PointList[], epsilon)
 //Находим точку с максимальным расстоянием от прямой между первой и последней точками набора
 dmax = 0
 index = 0
 for i = 2 to (length(PointList) - 1)
  d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
  if d > dmax
   index = i
   dmax = d
  end
 end
 
 //Если максимальная дистанция больше, чем epsilon, то рекурсивно вызываем её на участках
 if dmax >= epsilon
  //Recursive call
  recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
  recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
  
  // Строим итоговый набор точек
  ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
 else
  ResultList[] = {PointList[1], PointList[end]}
 end
 
 // Возвращаем результат
 return ResultList[]
end

Применение

Алгоритм применяется для обработки векторной графики и при генерализации карт (en).

Кроме того, применяется в робототехнике^[1] для обработки результатов работы кругового лазерного дальномера и поэтому также называется алгоритмом разбиения и слияния.

Сложность

Ожидаемая сложность алгоритма может быть оценена выражением $T(n) = 2T\left(\frac{n}{2}\right) + O(n)$, которая упрощается (как следствие Master Theorem) в $T(n) \in \Theta(n\log n)$. Однако в худшем случае сложность алгоритма $O\left(n^2\right)$.

Документы

• Urs Ramer, «An iterative procedure for the polygonal approximation of plane curves», Computer Graphics and Image Processing, 1(3), 244—256 (1972) (DOI: 10.1016/S0146-664X(72)80017-0)

• David Douglas & Thomas Peucker, «Algorithms for the reduction of the number of points required to represent a digitized line or its caricature», The Canadian Cartographer 10(2), 112—122 (1973) (DOI: 10.3138/FM57-6770-U75U-7727)

• John Hershberger & Jack Snoeyink, «Speeding Up the Douglas-Peucker Line-Simplification Algorithm», Proc 5th Symp on Data Handling, 134—143 (1992). UBC Tech Report TR-92-07 available at http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07

• R.O. Duda and P.E. Hart, «Pattern classification and scene analysis», (1973), Wiley, New York (http://rii.ricoh.com/~stork/DHS.html)

• Реализация алгоритма на Python http://mappinghacks.com/code/dp.py.txt

Ссылки

1. ↑ Nguyen and Martinelli and Siegwart A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics (2005).

Связать^?

На эту статью не ссылаются другие статьи Википедии. Пожалуйста, воспользуйтесь подсказкой и установите ссылки в соответствии с принятыми рекомендациями.