Ramer–Douglas–Peucker algorithm: Difference between revisions

Revision as of 15:56, 23 August 2021

Revision as of 14:27, 19 December 2021

Line 22:

=== Pseudocode ===

(Assumes the input is a one-based array)

<source lang="python">

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

Link # source: https://karthaus.nl/rdp/

// Find the point with the maximum distance

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

dmax = 0

//# Find the point with the maximum distance

index = 0

enddmax = length(PointList)0

dmaxindex = 0

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

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

}

}

ResultList[] = empty;

// 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...length(recResults1) - 1], recResults2[1...length(recResults2)]}

} '''else''' {

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

}

// Return the result

'''return''' ResultList[]

'''end'''

ResultList[] = empty;

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

//# 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...length(recResults1) - 1], recResults2[1...length(recResults2)]}

} else {

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

}

//# Return the result

'''return''' ResultList[]

</source>

== Application ==