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:

• Do you want the convex hull? - The simplest way to simplify a polygon is to take the convex hull of its vertices (see Section ). The convex hull removes all internal concavities from the polygon. If you were simplifying a robot model for motion planning, this is a good thing, because you are unlikely to be able to take advantage of the concavities in finding paths. If you were building an OCR system, the convex hull would be disastrous, because the concavities of characters provide most of the interesting features. An `X' would be identical to an `I', since both hulls are boxes. Another problem is that if the polygon is already convex, taking the convex hull will do nothing to simplify it further.    
• Am I allowed to insert or just delete points? - What is typically needed is a way to represent the object as well as possible using only a given number of vertices. The simplest approaches employ local modifications to the boundary of the polygon, in order to reduce the vertex count. For example, if three consecutive vertices form a small-area triangle or define an extremely large angle, the center vertex can be deleted and replaced with an edge without severely distorting the polygon.

  Methods that only delete vertices quickly melt the shape into unrecognizability, however. More robust heuristics move vertices around to cover up the gaps that are created by deletions. Such ``split-and-merge'' heuristics can do a decent job, although nothing is guaranteed. Better results are likely by using the Douglas-Peucker algorithm, described below.  

• Must the resulting polygon be intersection-free? - A serious drawback of such incremental procedures is that they fail to ensure simple polygons, those without self-intersections. Thus the ``simplified'' polygon may have artifacts that look ugly and that may cause problems for subsequent routines working on the polygon. If simplicity is important, you should test all the line segments of your polygon for any pairwise intersections, as discussed in Section .   

  An approach to polygon simplification that guarantees a simple approximation involves computing minimum-link paths. The link distance of a path between points and t is the number of straight segments on the path. An as-the-crow-flies path has a link distance of one. In general, the link distance is one more than the number of turns. The link distance between points and t in a scene with obstacles is defined by the minimum link distance over all paths from to t.  

  The link distance approach ``fattens'' the boundary of the polygon by some acceptable error window (see Section ) in order to construct a channel around the polygon and then constructs the minimum-link path through this channel.   The minimum-link cycle in this channel represents the simplest polygon that never deviates from the original boundary by more than . It constructs a globally optimal simplification that will not self-intersect, at the cost of implementation and time complexity.

• Are you given an image to clean up instead of a polygon to simplify? - The conventional, nongeometric approach to cleaning up noise from a digital image is to take the Fourier transform of the image, filter out the high-frequency elements, and then take the inverse transform to recreate the image. See Section for details on the fast Fourier transform.   

  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 and of polygon P, and propose the degenerate polygon 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 http://www.cs.unc.edu/ 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 ) 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 http://hrl.harvard.edu/people/postdocs/rlo/rlo.dir/rlo-soft.html.     

Notes: See [HG95] for a thorough survey of algorithms for shape simplification. It is also available from http://www.cs.cmu.edu/afs/cs/user/ph/www/heckbert.html, 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 ), convex hull (see page ).