Douglas-Peucker Algorithm, line simplification by #of points

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

DouglasPeuckerInv returns a simplifed curve with a target number of points and the epsilon to reach this target number.

It is sometimes not reversible, since sometimes no epsilon will satisfy a certain target number and sometimes a few points with smallest perpendicular distance are revomed directly, without Douglas-Peuker algorithm.

Input:

• points: List of points, double, N x [X, Y]

You may add identifiers for the points, then List = N x [X, Y, id]

• target: number of points for the output curve, integer number scalar.

Output:

• PointsOut: List of points for the simplified curve, target x [X, Y],

or target x [X, Y, id] if identifiers were included.

• epsilon: No original point has a larger perpendicular distance epsilon to the simplified curve.

The maximal perpendicular distance to the original is never larger than epsilon, but may be considerably smaller.

If you need the exact maximal perpendicular distance, run afterwards 'epsilonExact.m'.

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];
target = 5;% Number of points for the resulting curve
[PointsOut, epsilon] = DouglasPeuckerInv(Points,target);
figure(1); 
plot(X,Y,'.r-',PointsOut(:,1),PointsOut(:,2),'+b--');
grid on; 
axis equal

A demo file is included.