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

Question

Я хотел бы реализовать Ramer–Douglas–Peucker_algorithm в 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 :: векторы для массивов. Я думаю, что я буду использовать std :: copy, а затем нажмите или поп в соответствии с тем, что говорит алгоритм.

Благодаря

Answer 1

The OrthogonalDistance показано на рисунке:

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

Расстояние от точки до линии Usally-то вроде этого:

alt text http://dida.fauser.edu/matetri/donati/retta/formdist.gif

где х0 и у0 координаты внешней точки и , б , c - коэффициент уравнения вашей линии.

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

Answer 2

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

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

Answer 3

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

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

это это то, что ищете.

Answer 4

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

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

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

Answer 5

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

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

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