Home > Research > Line Simplification

Brief Description

When displaying maps, we frequently want to simplify the representation of linear features. There are many algorithms for simplification in the literature, but most have the potential for introducing intersections or topological changes in the data. The above applet uses an algorithm that runs in O(n log n) time, and does not introduce any intersections or topological changes.

The above applet simplifies polylines by representing safe sets by a single segment. The safe sets are identified using the greedy cone method described in "Safe Sets for Line Simplification". The dark blue line is the simplification of the light blue line. The vertices are drawn in red, the Delaunay triangulation is orange, and the Voronoi windows are green.

Instructions

• Click a mouse button to add points in a polyline.
• Shift-click to start a new polyline.
• Use the check boxes at the bottom to show/hide various features.

Notes

• I did not use an efficient Delaunay triangulation method for this demo, and I recalculate everything each time a point is added.
• I am still working out a few bugs in the Delaunay triangulation code.

Related Publications

• "Safe Sets for Line Simplification", Andrea Mantler and Jack Snoeyink,
  Slides as presented at the 10th Annual Fall Workshop on Computational Geometry, October 2000.

Support

This material is based upon work supported by the National Science Foundation under Grant No. 9988742.