Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 19:20, 10 December 2019

Revision as of 09:30, 18 December 2019

Line 17:

[[File:RDP, varying epsilon.gif|thumb|The effect of varying epsilon in a parametric implementation of RDP]]

=== Non-parametric Ramer-Douglas-PeuckerRamer–Douglas–Peucker ===

The choice of ''&epsilon;'' is usually user-defined. Like most line fitting / polygonal approximation / dominant point detection methods, it can be made non-parametric by using the error bound due to digitization / quantization as a termination condition.<ref>{{cite journal |last1 = Prasad |first1 = Dilip K. |first2 = Maylor K.H. |last2 = Leung |first3 = Chai |last3 = Quek |first4 = Siu-Yeung |last4 = Cho |title = A novel framework for making dominant point detection methods non-parametric |journal = Image and Vision Computing |year = 2012 |volume = 30 |issue = 11 |pages = 843–859 |doi = 10.1016/j.imavis.2012.06.010 }}</ref>

=== Pseudocode ===

(Assumes the input is a one-based array)

'''function''' DouglasPeucker(PointList[], epsilon)

// Find the point with the maximum distance

dmax = 0

index = 0

end = length(PointList)

'''for''' i = 2 to ( end - 1) {

d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))

'''if''' ( d > dmax ) {

index = i

dmax = d

Line 38:

// If max distance is greater than epsilon, recursively simplify

'''if''' ( dmax > epsilon ) {

// Recursive call

recResults1[] = DouglasPeucker(PointList[1...index], epsilon)

Line 45:

// Build the result list

ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]}

} '''else''' {

ResultList[] = {PointList[1], PointList[end]}

}

// Return the result

'''return''' ResultList[]

'''end'''

link Link: https://karthaus.nl/rdp/

== Application ==