dp-simplify — Douglas-Peucker simplification of polylines


dp-simplify [-h ] [-m min] [-o file] [-s char] [-t tol] [-v ] [-V ] file


This small program acts to simplify polyline data using the algorithm of Douglas-Peucker. The program reads files containing the polyline's vertices (specified as coordinate-pairs, separated by whitespace, one pair to a line), removes vertices up to a user-specified tolerance, and writes the simplified vertex-set in same format as the input.

Douglas-Peucker polyline simplification can result in a huge reduction in the number of vertices, saving storage and subsequent processing costs. Applications include data-reduction, cartography and the creation of client-side image maps.

The dp-simplify program will read (and write) files of multiple polylines, each polyline separated by a line containing only a #-character (the character can be set with the -s option). The intention is for compatibility with the files typically used with the GMT(1) mapping toolset.


-h, --help

Print brief help.

-m, --min integer

Suppress output of polylines with fewer than the specified number of vertices. This option is useful when the input data are polygons and one wishes to avoid degenerate (2-point) polygons in the output.

-o, --output file

Write the output to file, rather than stdout.

-s, --sepchar character

Specify the polyline separation character. The character will be expected in input (as the first character of a line) and is written in output.

-t, --tolerance float

Specify the tolerance (in the same units as the polyline coordinates) that the output must satisfy.

-v, --verbose

Verbose operation.

-V, --version

Version information.


To decimate UK Ordnance Survey polygon data in the file ospoly.xy, with a tolerance of 100m and rejecting all polygons with less than 10 vertices:

dp-simplify -t100 -m10 -v -o dec.xy ospoly.xy


There are reports in the literature suggesting that a recursive implementation of the algorithm (as used in the program) may exhaust execution stack space, given sufficiently hostile input data.

The program will give strange results if the input pairs specify geographic, rather than projected coordinates.


J.J. Green, using code written by Dan Sunday (thanks Dan).



example decimation