Douglas-Peucker Algorithm, line simplification by distance

版本 1.2 (3.9 KB) 作者: Peter Seibold
This algorithm keeps with fewer points the shape of the original track as good as possible without moving the remaining original points.
0.0
(0)
16.0 次下载
更新时间 2024/8/20

查看许可证

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
致谢

参考作品: Douglas-Peucker Algorithm

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

版本 已发布 发行说明
1.2

Changed title
1.1

Modified demo and included function for the exact max. perpendicular distance.

1.0.0