File Exchange

## Line Simplification

version 1.4 (6.03 KB) by

Recursive Douglas-Peucker Polyline Simplification (Iterative Endpoint Fit)

4.88889
9 Ratings

Updated

dpsimplify uses the recursive Douglas-Peucker line simplification algorithm to reduce the number of vertices in a polyline according to a specified tolerance. The algorithm is also know as Iterative Endpoint Fit algorithm. dpsimplify can handle polylines and polygones in 2d and higher dimensions.

The submission now contains another m-file (dpsimplify_octave.m) that has been slightly modified to run with GNU Octave.

Syntax:

[ps,ix] = dpsimplify(p,tol)

where p is a nxm matrix that contains n vertices in m dimensions.

http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

Charles Karney

### Charles Karney (view profile)

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

p=[0,-1,1,2; 0,0.05,0.1,0]';
q=dpsimplify(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.

--Charles

Elena Provaggi

Mircea Stoica

### Mircea Stoica (view profile)

Wolfgang Schwanghart

### Wolfgang Schwanghart (view profile)

@Mehdi: Thanks for your input. This algorithm assumes all data to be valid, thus there is no treatment of outliers.

Mehdi

### Mehdi (view profile)

Thanks for sharing
test this data
x=ones(1,16);x(16)=1.5;
y=1:numel(x);

Do you have any idea for tackling outliers(last point in this data)?

Zhouxin Xi

### Zhouxin Xi (view profile)

Alessandro Masullo

ykremer Kremer

### ykremer Kremer (view profile)

Works great, thank you!

ykremer Kremer

Antony37

### Antony37 (view profile)

Hi Wolfgang,
Thank you..:)

Regards,
Antony

Wolfgang Schwanghart

### Wolfgang Schwanghart (view profile)

@Antony37: Simplifyrec basically does one step shown here
http://en.wikipedia.org/wiki/File:Douglas_Peucker.png
It is called recursively so that the entire sequence shown in the picture is computed.

Antony37

### Antony37 (view profile)

Hi Wolfgang,
Can you explain the logic under the function 'simplifyrec'?

Mate

Daniel

Brandon

### Brandon (view profile)

AndreasChr Christ

### AndreasChr Christ (view profile)

Hi Wolfgang,
Regards
Andreas

Wolfgang Schwanghart

### Wolfgang Schwanghart (view profile)

Hi Andreas,

unfortunately I do not have access to the mapping toolbox, so I cannot tell if the results will be the same for dpsimplify and reducem. In general, however, I think, you can replace reducem with this function.

Best regards,
Wolfgang

AndreasChr Christ

### AndreasChr Christ (view profile)

Hi Wolfgang,
I have got cell tracking algorithm for microcopy images as m-files.
Unfortunately this uses MathLabs function "reducem". But we don't have the maps toolbox this function belongs to. Do you have experience if your dpsimplify could repolace reducem?
Yours
Andreas

Alistair Templeton

### Alistair Templeton (view profile)

Hi Wolfgang,
I wanted to simplify a contour as exported from a piece of imaging software which was way oversampled. Your program completely plugged and played, perfect!

Cheers

Wolfgang Schwanghart

The file has been updated so that the function can handle polylines, where the first and last vertex have the same coordinates. Just wait a short time until the updated version from 22. August appears.

Wolfgang Schwanghart

Hi Gwen,

you are right. I'll fix that as soon as possible.

Thanks,
Wolfgang

Gwendolyn Fisch

Hi,

the implementation fails if start and end point of the given line are the same.

Gwen