Douglas-Peucker line simplification algorithm implementation by Jack Snoeyink
DPsimp is a Douglas-Peucker line simplification alogorithm implementation
by John Hershberger and Jack Snoeyink. They analyze the line
simplification algorithm reported by Douglas and Peucker and show that its
worst case is quadratic in n, the number of input points. The algorithm is
based on path hulls, that uses the geometric structure of the problem to
attain a worst-case running time proportional to nlog_2(n), which is the
best case of the Douglas algorithm. Complete C code is given and the two
algorithms are compared theoretically, by operation counts, and
practically, by machine timings.
Download Files (local site)Jack Snoeyink's siteLink to source file
Problem Links
This page last modified on 2008-07-10
.
www.algorist.com
