The Ramer–Douglas–Peucker algorithm (RDP) is an algorithm for reducing the number of points in a curve that is approximated by a series of points. The initial form of the algorithm was independently suggested in 1972 by Urs Ramer and 1973 by David Douglas and Thomas Peucker and several others in the following decade. This algorithm is also known under the names Douglas–Peucker algorithm, iterative end-point fit algorithm and split-and-merge algorithm. [Source Wikipedia]
The classic Douglas-Peucker line-simplification algorithm is recognized as the one that delivers the best perceptual representations of the original lines.
The advantage of this algorithm is that it keeps with fewer points the shape of the original track (nearly) as good as possible without moving the remaining original points.
The simplification is done by the given max. perpendicular distance epsilon of an original line point to the simpifed line.
Input:
- Points: List of Points, double, N x [x, y]
- epsilon: distance dimension, specifies the similarity between the original curve and the approximated (smaller the epsilon, the curves more similar), integer scalar.
Remark: You may add identifiers for the points, then List = N x [x, y, id]
Output:
result: List of Points for the approximated curve M x [x, y] or M x [x, y, id] if identifiers were included.
If you need the exact maximal perpendicular distance, run afterwards 'epsilonExact.m' as in the included demo file.
Example:
x = [8; 4; 5; 1; 0; 4; 8; 12; 11];
y = [0; -2; 2; 4; 10; 14; 8; 2; 0];
id = (1:9)';%identifier
Points = [x,y,id];
epsilon = 3;% Largest perpendicular distance from the new track to the original track
result = DouglasPeuckerB(Points,epsilon);
figure(1); plot(x,y,'.r-',result(:,1),result(:,2),'.b--'); grid on; axis equal
-------------------------------------------------------
Original code by Reza Ahmadzadeh (2017), https://de.mathworks.com/matlabcentral/fileexchange/61046-douglas-peucker-algorithm
Altered code by Peter Seibold (2024) (Faster, vertical vectors in/out and identifiers)
引用格式
Peter Seibold (2024). Douglas-Peucker Algorithm, line simplification by distance (https://www.mathworks.com/matlabcentral/fileexchange/171489-douglas-peucker-algorithm-line-simplification-by-distance), MATLAB Central File Exchange. 检索来源 .
MATLAB 版本兼容性
创建方式
R2020a
兼容任何版本
平台兼容性
Windows macOS Linux标签
致谢
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!