File Exchange

image thumbnail

Line Simplification

version 1.4.0.0 (6.03 KB) by Wolfgang Schwanghart
Recursive Douglas-Peucker Polyline Simplification (Iterative Endpoint Fit)

10 Downloads

Updated 13 Jul 2010

View Version History

View License

Editor's Note: This file was selected as MATLAB Central Pick of the Week

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.

For additional information on the algorithm follow this link
http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

Cite As

Wolfgang Schwanghart (2020). Line Simplification (https://www.mathworks.com/matlabcentral/fileexchange/21132-line-simplification), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (28)

Luca Speranza

Many thanks!

Bram de Kleuver

Bram Mast

Hi Wolfgang

I have a mix of very different polygon shapes. When giving a large tolerance level, it works well for big geometries, but it this case the smaller ones are simplified to a line.
How can I avoid, polygons to be simplefied to a single line ?

Giovanni Florio

Min

Fast, efficient and simple. This algorithm does exactly what I need. Thanks!

Nick

Charles Karney

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

Wolfgang Schwanghart

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

Mehdi

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)?

jigsaw

Alessandro Masullo

ykremer Kremer

Works great, thank you!

ykremer Kremer

Antony37

Hi Wolfgang,
Thank you..:)

Regards,
Antony

Wolfgang Schwanghart

@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

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

Mate

Daniel

Brandon

AndreasChr Christ

Hi Wolfgang,
thanks for your answer. Iwill try it
Regards
Andreas

Wolfgang Schwanghart

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

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

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

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

Community Treasure Hunt

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

Start Hunting!