Components

 
  home
     

Projects

Products

Components

Contact Us

Design Background

Curriculum Vitae

Forum

Blog

Links

 

 

Polyline simplification using Douglas-Peucker algorithm
Added: 22Mar2003
Author: Nils Haeck M.Sc.

Introduction

This page describes an algorithm with which polylines consisting of many points can be reduced to a simplified form. This can be useful in situations where your graphical application must draw many polylines and time becomes an issue, like cartographic applications.

A well-known algorithm that implements polyline simplification is the classical Douglas-Peucker algorithm [Douglas & Peucker, 1973]. More recently, improvements on the original algorithm have been written. [Hershberger & Snoeyink, 1992].

These improvements have not been implemented in the algorithm on this page, in order to avoid making the code too complex. Hence, the code on this page is not the most optimal code for polyline simplification. However, in practice the original algorithm works virtually as fast as the more optimized one. More information about this subject can be found through the links below.

By downloading the library you agree to the terms in the license.

The source contains the DouglasPeuckers.pas unit with the algorithm implementation as well as an example application.

Two versions of the algorithm are supplied; one version for polylines consisting of floating point 3D vertices, and one version for polylines consisting of integer 2D vertices. The latter is ideal for Windows GDI style "TPoint" implementations.

Support is not included, but can be purchased separately. Please contact us by email for more information.

References

  • David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112-122 (1973)

Related Links

Polyline simplification by Dan Sunday
This article has served as the example for the Delphi implementation on this page. The article contains some very useful information, as well as a C++ implementation.

Line smoothing package using Bezier curves
This package provides source code for customizable line smoothing, using Bezier curves. The package provides simple-to-integrate freehand line smoothing tools for use in vectorial or photo editors.

 

   Page last changed: 27Mar2010 © Copyright 2002-2010 SimDesign