Douglas-Peucker Algorithm, line simplification by distance

This algorithm keeps with fewer points the shape of the original track as good as possible without moving the remaining original points.

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)