Помогите с пониманием этого алгоритма

Question

Я хотел бы реализовать алгоритм Рамера-Дугласа-Пеккера в C ++.

Псевдокод выглядит так:

function DouglasPeucker(PointList[], epsilon)
 //Find the point with the maximum distance
 dmax = 0
 index = 0
 for i = 2 to (length(PointList) - 1)
  d = OrthogonalDistance(PointList[i], Line(PointList[1], PointList[end])) 
  if d > dmax
   index = i
   dmax = d
  end
 end

 //If max distance is greater than epsilon, recursively simplify
 if dmax >= epsilon
  //Recursive call
  recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
  recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

  // Build the result list
  ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
 else
  ResultList[] = {PointList[1], PointList[end]}
 end

 //Return the result
 return ResultList[]
end

Вот мое понимание до сих пор. Это рекурсивная функция, принимающая массив точек и порог расстояния.

Затем он перебирает текущие точки, чтобы найти точку с максимальным расстоянием.

Я немного растерялся с функцией Ортографическое расстояние. Как мне это вычислить? Я никогда не видел, чтобы функция расстояния принимала отрезок в качестве параметра.

Думаю, что со мной все будет в порядке, я буду использовать std :: vectors для массивов. Я думаю, что я буду использовать std :: copy и затем нажимать или выдавливать в соответствии с тем, что говорит алгоритм.

Спасибо

Answer 1

OrthogonalDistance показано на этом рисунке:

Таким образом, это расстояние от вашей точки до точки на линии, которая является проекцией этой точки налиния.

Расстояние от точки до линии обычно примерно такое:

альтернативный текст http://dida.fauser.edu/matetri/donati/retta/formdist.gif

где x0 и y0 - координаты внешней точки, а a , b , c - коэффициент уравнения вашей линии.

Это то, что я помню из школы, давным-давно.

Answer 2

Мне не ясно, хотите ли вы, чтобы расстояние от точки до (бесконечной) линии, проходящей через две точки, или расстояние до отрезка, определенного точками, но я подозреваю, что это последнее.

Рассмотрим несколько надуманный пример точек (0,0) (1,0) и (10, t), где t мало. Расстояние (10, t) от прямой через первые две точки (то есть ось x) равно t, а расстояние (10, t) от отрезка с конечными точками (0,0) и (1,0) ) является гипотетой (9, т) ~ 9. Так что, если вы использовали расстояние до линии, есть опасность, что Алгоритм выше не будет разделяться на (10, т).

Метод, упомянутый Jethro выше, обрабатывает как линии, так и отрезки.

Answer 3

Краткое описание требуемой математики можно найти здесь . Просто поймите, что вы можете поменять слово «Ортогональный» на «Перпендикулярный» при работе с 2D. На связанном сайте есть инструкции для линий, определяемых двумя точками, а также линий, определяемых формой уклона-пересечения.

Краткая версия воспроизводится здесь: Если линия представлена ​​в пересечении наклона от: ax + посредством + c = 0, а точка представлена ​​x0, y0, то функция, которая даст ортогональное расстояние:

abs(a*x0 + b*y0 + c)/sqrt(a*a + b*b) 

Answer 4

Посмотрите учебник topcoder и метод

double linePointDist(point A, point B, point C, bool isSegment);

. Это то, что вы ищете.

Answer 5

Ортогональное расстояние от точки P до линии L определяется расстоянием между точкой P и точкой P2, где P2 - ортогональная проекция P на линию L.

Способ вычисления этого значения зависит от размера пространства, в котором вы работаете, но если он 2D, вы сможете это выяснить, нарисовав пример на листе бумаги!