next up previous contents index CD CD Algorithms
Next: Shape Similarity Up: Computational Geometry Previous: Polygon Partitioning

Simplifying Polygons



Input description: A polygon or polyhedron p, with n vertices.

Problem description: Find a polygon or polyhedron p' with n' vertices, where the shape of p' is close to p and n' < n.

Discussion: Polygon simplification has two primary applications. The first is in cleaning up a noisy representation of a polygon, perhaps obtained by scanning a picture of an object. By processing it, we hope to remove the noise and reconstruct the original object. The second is in data compression, where given a large and complicated object, we seek to simplify it by reducing detail. Ideally, we obtain a polygon with far fewer vertices that looks essentially the same. This can be a big win in computer graphics, where replacing a large model with a smaller model might have little visual impact but be significantly faster to render.      

Several issues arise in shape simplification:

  The Douglas-Plucker algorithm for shape simplification starts with a simple approximation and then refines it, instead of starting with a complicated polygon and trying to simplify it. Start by selecting two vertices tex2html_wrap_inline30372 and tex2html_wrap_inline30374 of polygon P, and propose the degenerate polygon tex2html_wrap_inline30376 as a simple approximation P'. Scan through each of the vertices of P, and select the one that is farthest from the corresponding edge of the polygon P'. Inserting this vertex adds the triangle to P' so as to minimize the maximum deviation from P. Points can be inserted until satisfactory results are achieved. This takes O(kn) to insert k points when |P|=n.

Simplification becomes considerably more difficult in three dimensions. For example, it is NP-complete to find the minimum-size surface separating two polyhedra. Higher-dimensional analogies of the planar algorithms discussed here can be used to heuristically simplify polyhedra. See the references below.  

Implementations: A program for automatically generating level-of-detail hierarchies for polygonal models is available from tex2html_wrap_inline30388 geom/envelope.html and is free for noncommercial use. The user specifies a single error tolerance, and the maximum surface deviation of the simplified model from the original model, and a new, simplified model is generated. This code preserves holes and prevents self-intersection.  

Yet another approach to polygonal simplification is based on simplifying and expanding the medial-axis transform of the polygon. The medial-axis transform (see Section gif) produces a skeleton of the polygon, which can be trimmed before inverting the transform to yield a simpler polygon. MAT [Ogn93] is a medial-axis transform code designed for 2D skeletonization and inversion of binary images, written by Robert Ogniewicz and available from     

Notes: See [HG95] for a thorough survey of algorithms for shape simplification. It is also available from, along with implementations.

The Douglas-Peucker incremental refinement algorithm [DP73] is the basis for most shape simplification schemes, with a faster implementation due to Hershberger and Snoeyink [HS94]. The link distance approach to polygon simplification is presented in [GHMS93]. Shape simplification problems become considerably more complex in three dimensions. Even finding the minimum-vertex convex polyhedron lying between two nested convex polyhedra is NP-complete [DJ92], although approximation algorithms are known [MS95b].

Testing whether a polygon is simple can be performed in linear time, at least in theory, as a consequence of Chazelle's linear-time triangulation algorithm [Cha91].  

Related Problems: Fourier transform (see page gif), convex hull (see page gif).    

next up previous contents index CD CD Algorithms
Next: Shape Similarity Up: Computational Geometry Previous: Polygon Partitioning

Mon Jun 2 23:33:50 EDT 1997