The Ramer–Douglas–Peucker algorithm, also known as the Douglas–Peucker algorithm and iterative end-point fit algorithm, is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points. It was one of the earliest successful algorithms developed for cartographic generalization.
The purpose of the algorithm is, given a curve composed of line segments (which is also called a Polyline in some contexts), to find a similar curve with fewer points. The algorithm defines 'dissimilar' based on the maximum distance between the original curve and the simplified curve (i.e., the Hausdorff distance between the curves). The simplified curve consists of a subset of the points that defined the original curve.
Algorithmedit
Simplifying a piecewise linear curve with the Douglas–Peucker algorithm.
The starting curve is an ordered set of points or lines and the distance dimension ε > 0.
The algorithm recursively divides the line. Initially it is given all the points between the first and last point. It automatically marks the first and last point to be kept. It then finds the point that is farthest from the line segment with the first and last points as end points; this point is obviously farthest on the curve from the approximating line segment between the end points. If the point is closer than ε to the line segment, then any points not currently marked to be kept can be discarded without the simplified curve being worse than ε.
If the point farthest from the line segment is greater than ε from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the farthest point and then with the farthest point and the last point, which includes the farthest point being marked as kept.
When the recursion is completed a new output curve can be generated consisting of all and only those points that have been marked as kept.
The effect of varying epsilon in a parametric implementation of RDP
Non-parametric Ramer–Douglas–Peuckeredit
The choice of ε is usually user-defined. Like most line fitting, polygonal approximation or dominant point detection methods, it can be made non-parametric by using the error bound due to digitization and quantization as a termination condition.[1]
Pseudocodeedit
Assuming the input is a one-based array:
# source: https://karthaus.nl/rdp/functionDouglasPeucker(PointList[],epsilon)# Find the point with the maximum distancedmax=0index=0end=length(PointList)fori=2to(end-1){d=perpendicularDistance(PointList[i],Line(PointList[1],PointList[end]))if(d>dmax){index=idmax=d}}ResultList[]=empty;# If max distance is greater than epsilon, recursively simplifyif(dmax>epsilon){# Recursive callrecResults1[]=DouglasPeucker(PointList[1...index],epsilon)recResults2[]=DouglasPeucker(PointList[index...end],epsilon)# Build the result listResultList[]={recResults1[1...length(recResults1)-1],recResults2[1...length(recResults2)]}}else{ResultList[]={PointList[1],PointList[end]}}# Return the resultreturnResultList[]
Applicationedit
The algorithm is used for the processing of vector graphics and cartographic generalization. It does not always preserve the property of non-self-intersection for curves which has led to the development of variant algorithms.[2]
The algorithm is widely used in robotics[3] to perform simplification and denoising of range data acquired by a rotating range scanner; in this field it is known as the split-and-merge algorithm and is attributed to Duda and Hart.[4]
Complexityedit
The running time of this algorithm when run on a polyline consisting of n – 1 segments and n vertices is given by the recurrence T(n) = T(i + 1) + T(n − i) + O(n) where i = 1, 2,..., n − 2 is the value of index in the pseudocode. In the worst case, i = 1 or i = n − 2 at each recursive invocation and this algorithm has a running time of Θ(n2). In the best case i = n/2 or i = n ± 1/2 at each recursive invocation in which case the running time has the well-known solution (via the master theorem for divide-and-conquer recurrences) of O(n log n).
Using (fully or semi-) dynamic convex hull data structures, the simplification performed by the algorithm can be accomplished in O(n log n) time.[5]
Under certain circumstances, the complexity can be reduced to O(n) using an iterative approach.[6]
Similar algorithmsedit
Alternative algorithms for line simplification include:
Ramer, Urs (1972). "An iterative procedure for the polygonal approximation of plane curves". Computer Graphics and Image Processing. 1 (3): 244–256. doi:10.1016/S0146-664X(72)80017-0.
Douglas, David; Peucker, Thomas (1973). "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature". Cartographica: The International Journal for Geographic Information and Geovisualization. 10 (2): 112–122. doi:10.3138/FM57-6770-U75U-7727.
Hershberger, John; Snoeyink, Jack (1992). Speeding Up the Douglas–Peucker Line-Simplification Algorithm. Proceedings of the 5th Symposium on Data Handling. pp. 134–143. UBC Tech Report TR-92-07 available at http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07
Duda, R.O.; Hart, P.E. (1973). . New York: Wiley. Bibcode:1973pcsa.book.....D. Archived from the original on 2011-07-15.
Visvalingam, M.; Whyatt, J.D. (1992). Line Generalisation by Repeated Elimination of the Smallest Area (Technical report). Discussion Paper. Cartographic Information Systems Research Group (CISRG), The University of Hull. 10.
Referencesedit
^Prasad, Dilip K.; Leung, Maylor K.H.; Quek, Chai; Cho, Siu-Yeung (2012). "A novel framework for making dominant point detection methods non-parametric". Image and Vision Computing. 30 (11): 843–859. doi:10.1016/j.imavis.2012.06.010.
^Wu, Shin-Ting; Marquez, Mercedes (2003). "A non-self-intersection Douglas-Peucker algorithm". 16th Brazilian Symposium on Computer Graphics and Image Processing (SIBGRAPI 2003). Sao Carlos, Brazil: IEEE. pp. 60–66. CiteSeerX10.1.1.73.5773. doi:10.1109/SIBGRA.2003.1240992. ISBN978-0-7695-2032-2. S2CID 10163908.
^Nguyen, Viet; Gächter, Stefan; Martinelli, Agostino; Tomatis, Nicola; Siegwart, Roland (2007). "A comparison of line extraction algorithms using 2D range data for indoor mobile robotics" (PDF). Autonomous Robots. 23 (2): 97–111. doi:10.1007/s10514-007-9034-y. hdl:20.500.11850/9089. S2CID 35663952.
Boost.Geometry support Douglas–Peucker simplification algorithm
Implementation of Ramer–Douglas–Peucker and many other simplification algorithms with open source licence in C++
XSLT implementation of the algorithm for use with KML data.
You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page
Interactive visualization of the algorithm
Implementation in F#
Ruby gem implementation
JTS, Java Topology Suite, contains Java implementation of many algorithms, including the Douglas-Peucker algorithm
Rosetta Code (Implementations in many languages)
March 17, 2024
ramer, douglas, peucker, algorithm, also, known, douglas, peucker, algorithm, iterative, point, algorithm, algorithm, that, decimates, curve, composed, line, segments, similar, curve, with, fewer, points, earliest, successful, algorithms, developed, cartograph. The Ramer Douglas Peucker algorithm also known as the Douglas Peucker algorithm and iterative end point fit algorithm is an algorithm that decimates a curve composed of line segments to a similar curve with fewer points It was one of the earliest successful algorithms developed for cartographic generalization Contents 1 Idea 2 Algorithm 2 1 Non parametric Ramer Douglas Peucker 2 2 Pseudocode 3 Application 4 Complexity 5 Similar algorithms 6 See also 7 Further reading 8 References 9 External linksIdea editThe purpose of the algorithm is given a curve composed of line segments which is also called a Polyline in some contexts to find a similar curve with fewer points The algorithm defines dissimilar based on the maximum distance between the original curve and the simplified curve i e the Hausdorff distance between the curves The simplified curve consists of a subset of the points that defined the original curve Algorithm edit nbsp Simplifying a piecewise linear curve with the Douglas Peucker algorithm The starting curve is an ordered set of points or lines and the distance dimension e gt 0 The algorithm recursively divides the line Initially it is given all the points between the first and last point It automatically marks the first and last point to be kept It then finds the point that is farthest from the line segment with the first and last points as end points this point is obviously farthest on the curve from the approximating line segment between the end points If the point is closer than e to the line segment then any points not currently marked to be kept can be discarded without the simplified curve being worse than e If the point farthest from the line segment is greater than e from the approximation then that point must be kept The algorithm recursively calls itself with the first point and the farthest point and then with the farthest point and the last point which includes the farthest point being marked as kept When the recursion is completed a new output curve can be generated consisting of all and only those points that have been marked as kept nbsp The effect of varying epsilon in a parametric implementation of RDPNon parametric Ramer Douglas Peucker edit The choice of e is usually user defined Like most line fitting polygonal approximation or dominant point detection methods it can be made non parametric by using the error bound due to digitization and quantization as a termination condition 1 Pseudocode edit Assuming the input is a one based array source https karthaus nl rdp 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 gt dmax index i dmax d ResultList empty If max distance is greater than epsilon recursively simplify if dmax gt 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 Application editThe algorithm is used for the processing of vector graphics and cartographic generalization It does not always preserve the property of non self intersection for curves which has led to the development of variant algorithms 2 The algorithm is widely used in robotics 3 to perform simplification and denoising of range data acquired by a rotating range scanner in this field it is known as the split and merge algorithm and is attributed to Duda and Hart 4 Complexity editThe running time of this algorithm when run on a polyline consisting of n 1 segments and n vertices is given by the recurrence T n T i 1 T n i O n where i 1 2 n 2 is the value of index in the pseudocode In the worst case i 1 or i n 2 at each recursive invocation and this algorithm has a running time of 8 n2 In the best case i n 2 or i n 1 2 at each recursive invocation in which case the running time has the well known solution via the master theorem for divide and conquer recurrences of O n log n Using fully or semi dynamic convex hull data structures the simplification performed by the algorithm can be accomplished in O n log n time 5 Under certain circumstances the complexity can be reduced to O n using an iterative approach 6 Similar algorithms editAlternative algorithms for line simplification include Visvalingam Whyatt Reumann Witkam Opheim simplification Lang simplification Zhao SaalfeldSee also editCurve fittingFurther reading editRamer Urs 1972 An iterative procedure for the polygonal approximation of plane curves Computer Graphics and Image Processing 1 3 244 256 doi 10 1016 S0146 664X 72 80017 0 Douglas David Peucker Thomas 1973 Algorithms for the reduction of the number of points required to represent a digitized line or its caricature Cartographica The International Journal for Geographic Information and Geovisualization 10 2 112 122 doi 10 3138 FM57 6770 U75U 7727 Hershberger John Snoeyink Jack 1992 Speeding Up the Douglas Peucker Line Simplification Algorithm Proceedings of the 5th Symposium on Data Handling pp 134 143 UBC Tech Report TR 92 07 available at http www cs ubc ca cgi bin tr 1992 TR 92 07 Duda R O Hart P E 1973 Pattern Classification and Scene Analysis New York Wiley Bibcode 1973pcsa book D Archived from the original on 2011 07 15 Visvalingam M Whyatt J D 1992 Line Generalisation by Repeated Elimination of the Smallest Area Technical report Discussion Paper Cartographic Information Systems Research Group CISRG The University of Hull 10 References edit Prasad Dilip K Leung Maylor K H Quek Chai Cho Siu Yeung 2012 A novel framework for making dominant point detection methods non parametric Image and Vision Computing 30 11 843 859 doi 10 1016 j imavis 2012 06 010 Wu Shin Ting Marquez Mercedes 2003 A non self intersection Douglas Peucker algorithm 16th Brazilian Symposium on Computer Graphics and Image Processing SIBGRAPI 2003 Sao Carlos Brazil IEEE pp 60 66 CiteSeerX 10 1 1 73 5773 doi 10 1109 SIBGRA 2003 1240992 ISBN 978 0 7695 2032 2 S2CID 10163908 Nguyen Viet Gachter Stefan Martinelli Agostino Tomatis Nicola Siegwart Roland 2007 A comparison of line extraction algorithms using 2D range data for indoor mobile robotics PDF Autonomous Robots 23 2 97 111 doi 10 1007 s10514 007 9034 y hdl 20 500 11850 9089 S2CID 35663952 Duda Richard O Hart Peter E 1973 Pattern classification and scene analysis New York Wiley ISBN 0 471 22361 1 Hershberger John Snoeyink Jack 1992 Speeding Up the Douglas Peucker Line Simplification Algorithm PDF Technical report https gist github com stohrendorf aea5464b1a242adca8822f2fe8da6612External links editBoost Geometry support Douglas Peucker simplification algorithm Implementation of Ramer Douglas Peucker and many other simplification algorithms with open source licence in C XSLT implementation of the algorithm for use with KML data You can see the algorithm applied to a GPS log from a bike ride at the bottom of this page Interactive visualization of the algorithm Implementation in F Ruby gem implementation JTS Java Topology Suite contains Java implementation of many algorithms including the Douglas Peucker algorithm Rosetta Code Implementations in many languages Retrieved from https en wikipedia org w index php title Ramer Douglas Peucker algorithm amp oldid 1188346506, wikipedia, wiki, book, books, library,
