Реализации алгоритмов/Алгоритм Рамера — Дугласа — Пекера: различия между версиями
Содержимое удалено Содержимое добавлено
РоманСузи (обсуждение | вклад) начальная версия |
РоманСузи (обсуждение | вклад) дополнение |
||
Строка 3:
Суть алгоритма состоит в том, чтобы по данной ломаной, аппроксимирующей кривую, построить ломаную с меньшим числом точек. Алгоритм определяет расхождение, которое вычисляется по максимальному расстоянию между исходной и упрощённой кривыми. Упрощенная кривая состоит из подмножества точек, которые определяются из исходной кривой.
== Псевдокод ==
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
== Python ==
| |||