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 . It produces the most accurate generalization, but it is also more time-consuming.
15-462: [REDACTED] Look up RDP in Wiktionary, the free dictionary. RDP may refer to: Computing [ edit ] Ramer–Douglas–Peucker algorithm , an algorithm for polygonal simplification Recombination detection program , for analysing genetic recombination Recursive descent parser , a type of top-down parser Remote Desktop Protocol ,
30-432: A Microsoft remote access network protocol Reliable Data Protocol , a transport layer network protocol Organisations [ edit ] Rally for Democracy and Progress (disambiguation) , several political parties Democratic and Popular Rally (French: Rassemblement Démocratique et Populaire ), a Burkina Faso political party Radiodifusão Portuguesa , a subsidiary of Rádio e Televisão de Portugal ,
45-496: A subsidiary of Rádio e Televisão de Portugal , the public service broadcasting organisation of Portugal Other uses [ edit ] RDP (film) , Fujifilm photographic films Ratos de Porão , a Brazilian hardcore band Reconstruction and Development Programme , South Africa Recreational Dive Planner Roll of Distinguished Philatelists Kazi Nazrul Islam Airport , Andal, West Bengal, India, IATA code Bus Route Development Programme Topics referred to by
60-436: A type of top-down parser Remote Desktop Protocol , a Microsoft remote access network protocol Reliable Data Protocol , a transport layer network protocol Organisations [ edit ] Rally for Democracy and Progress (disambiguation) , several political parties Democratic and Popular Rally (French: Rassemblement Démocratique et Populaire ), a Burkina Faso political party Radiodifusão Portuguesa ,
75-426: Is attributed to Duda and Hart . 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 yields a running time of O ( n ) . In
90-467: Is different from Wikidata All article disambiguation pages All disambiguation pages RDP [REDACTED] Look up RDP in Wiktionary, the free dictionary. RDP may refer to: Computing [ edit ] Ramer–Douglas–Peucker algorithm , an algorithm for polygonal simplification Recombination detection program , for analysing genetic recombination Recursive descent parser ,
105-449: Is different from Wikidata All article disambiguation pages All disambiguation pages Ramer%E2%80%93Douglas%E2%80%93Peucker 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
120-425: 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 choice of ε
135-414: 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. Assuming the input is a one-based array: The algorithm is used for the processing of vector graphics and cartographic generalization . It is recognized as the one that delivers
150-418: The best case, i = n / 2 or i = n ± 1 / 2 at each recursive invocation yields a running time 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. Given specific conditions related to the bounding metric, it is possible to decrease
165-403: The best perceptual representations of the original lines. But a self-intersection could occur if the accepted approximation is not sufficiently fine which led to the development of variant algorithms. The algorithm is widely used in robotics 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
SECTION 10
#1732845462803180-412: The point that is farthest from the line segment with the first and last points as end points; this point is always 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
195-444: The public service broadcasting organisation of Portugal Other uses [ edit ] RDP (film) , Fujifilm photographic films Ratos de Porão , a Brazilian hardcore band Reconstruction and Development Programme , South Africa Recreational Dive Planner Roll of Distinguished Philatelists Kazi Nazrul Islam Airport , Andal, West Bengal, India, IATA code Bus Route Development Programme Topics referred to by
210-543: The same term [REDACTED] This disambiguation page lists articles associated with the title RDP . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=RDP&oldid=1254733425 " Categories : Disambiguation pages Political party disambiguation pages Hidden categories: Articles containing French-language text Articles containing Portuguese-language text Short description
225-543: The same term [REDACTED] This disambiguation page lists articles associated with the title RDP . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=RDP&oldid=1254733425 " Categories : Disambiguation pages Political party disambiguation pages Hidden categories: Articles containing French-language text Articles containing Portuguese-language text Short description
#802197