Line Simplification Literature Review?
ph+ at cs.cmu.edu
Tue Jan 30 17:26:24 PST 2001
Steve Zoraster wrote:
> I have not been paying attention to the state-of-the-art in automated 2D
> line simplification for some time. Could someone recommend an up-to-date
> review article on this topic?
If by "line simplification" you mean taking a polyline (piecewise-linear
curve) and approximating it with a new polyline with fewer line segments,
then my survey is relevant:
Survey of Polygonal Surface Simplification Algorithms,
Paul S. Heckbert and Michael Garland, tech. report,
CS Dept., Carnegie Mellon U., 1997,
that is available at
Let me know if you have trouble with the above FTP site.
The survey covers curve simplification briefly.
My high-level conclusions:
* many literatures have explored this topic, including cartography,
computer graphics, pattern recognition, image processing, computer vision,
* cartography calls this topic "generalization"
* there's been a lot of redundant work in this area
* the Douglas-Peucker algorithm is the most widely-used
4205 Newell-Simon Hall
Computer Science Dept.
Carnegie Mellon University
Pittsburgh PA 15213-3891, USA
ph at cs.cmu.edu
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce