File Exchange

image thumbnail

Douglas-Peucker Algorithm

version 1.1.0.0 (57.8 KB) by Reza Ahmadzadeh
The Douglas–Peucker algorithm reduces the number of points in a curve.

12 Downloads

Updated 07 Jan 2017

View License

% 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]
%
% Input:
% Points: List of Points 2xN
% epsilon: distance dimension, specifies the similarity between
% the original curve and the approximated (smaller the epsilon,
% the curves more similar)
% Output:
% result: List of Points for the approximated curve 2xM (M<=N)
%

Comments and Ratings (3)

it do not work for polygons ?or closed objects ?

Thanks for this routine. Here's a failure case:

p=[0,-1,1,2; 0,0.05,0.1,0];
q=DouglasPeucker(p,0.2);
plot(p(1,:),p(2,:),q(1,:),q(2,:));
axis equal;

The problem arises because you only consider the perpendicular distance from the simplified line. You need also to consider the actual distance from the end points when the original points lie to the left or right of the simplified line.

Also, please consider an extension of "doing the right thing" when NaNs are present. These allow breaks in a line when plotting within Matlab. These breaks should be preserved (i.e., D-P simplification should be applied to each continuous segment) and adjacent NaN should be compressed to a single NaN. Thanks for your consideration.

--Charles

jmrplens

Perfect work. :)

Updates

1.1.0.0

snapshot added.

MATLAB Release Compatibility
Created with R2008a
Compatible with any release
Platform Compatibility
Windows macOS Linux