幫助理解該算法

我想在C++中實現Ramer–Douglas–Peucker_algorithm。幫助理解該算法

僞代碼如下所示：

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，然後根據算法說的推或者彈出。

由於

來源

2010-08-16 jmasterx

那麼，是不是OrthogonalDistance應該計算一個點與線的正交距離？當然一條線包含2點。你可以用一些基本的三角函數來計算它。 – futureelite7 2010-08-16 17:20:32

的OrthogonalDistance顯示在這張照片：

alt Orthogonal

所以這是從點的距離，並在其上線是點的投影線的點。

從點到直線的距離是usally這樣的：

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

其中X0和Y0是外部點的座標和一個，b ，c是你生產線方程的係數。

這就是我很久以前從學校記得的東西。

來源

2010-08-16 17:27:44 dierre

對於漂亮的圖片：p – jmasterx 2010-08-16 17:48:19

從點P至線L正交距離由點P和點P2之間的距離，其中P 2爲P的上線的正投影L.

你如何定義計算這個值取決於你工作的空間的尺寸，但如果它是2D的，你應該能夠通過在一張紙上畫一個例子來解決這個問題！

來源

2010-08-16 17:24:05

好吧我現在知道了，我知道它從點到線的距離 – jmasterx 2010-08-16 17:27:52

看那topcoder教程，它它你找什麼

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

方法。

來源

2010-08-16 17:27:05 jethro

對所需數學的簡要描述可以找到here。只要意識到在處理2D時可以將「Orthogonal」一詞換成「Perpendicular」。鏈接的站點有由兩點定義的線以及由斜截式定義的線。

簡短版本在這裏轉載：如果斜線表示斜線截距爲：ax + by + c = 0，並且點由x0，y0表示，那麼給出正交距離的函數是：

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

來源

2010-08-16 17:36:32 Andres

您是否想點通過兩點（無限）線，或由點定義的線段的距離的距離，但我懷疑它的後者目前尚不清楚對我。

考慮點（0,0）（1,0）和（10，t）有點人爲的例子，其中t很小。通過前兩個點（即x軸）的線與（10，t）的距離爲t，而距終點（0,0）和（1,0）的線段的距離（10，t））是hypot（9，t）〜9.所以如果你使用的是距離線，上面的算法有可能不會在（10，t）處分裂。

jethro上面提到的方法處理線段和線段。

來源

2010-08-17 14:11:35 dmuir

幫助理解該算法

回答

相關問題