next up previous contents index CD CD Algorithms
Next: Simplifying Polygons Up: Computational Geometry Previous: Medial-Axis Transformation

Polygon Partitioning



Input description: A polygon or polyhedron P.

Problem description: How can P be partitioned into a small number of simple (typically convex) pieces?

Discussion: Polygon partitioning is an important preprocessing step for many geometric algorithms, because most geometric problems are simpler and faster on convex objects than on nonconvex ones. We are better off whenever we can partition a nonconvex object into a small number of convex pieces, because it is easier to work with the pieces independently than with the original object.  

Several flavors of polygon partitioning arise, depending upon the particular application:

The Hertel-Mehlhorn heuristic for convex decomposition using diagonals is simple, efficient, and always produces no more than four times the minimum number of convex pieces. It starts with an arbitrary triangulation of the polygon and then deletes a chord that leaves only convex pieces. The decision of whether a chord deletion will create a nonconvex piece can be made locally from the chords and edges surrounding the chord, in constant time. A vertex in a polygon is reflex if the internal angle is greater than 180 degrees. We can delete any chord that does not create a reflex vertex.   

I recommend using this heuristic unless it is critical for you to absolutely minimize the number of pieces. By experimenting with different triangulations and various deletion orders, you may be able to obtain somewhat better decompositions.  

Dynamic programming may be used to minimize the number of diagonals used in the decomposition. The simplest implementation, which maintains the number of pieces for all tex2html_wrap_inline30325 subpolygons split by a chord, runs in tex2html_wrap_inline30327 . Faster algorithms use fancier data structures, running in tex2html_wrap_inline30329 time, where r is the number of reflex vertices. An tex2html_wrap_inline30331 algorithm that further reduces the number of pieces by adding interior vertices is cited below, although it is complex and presumably difficult to implement.

Implementations: Many triangulation codes start by finding a trapezoidal or monotone decomposition of polygons. Further, a triangulation is a simple form of convex decomposition. Check out the codes in Section gif as a starting point for most any decomposition problem.    

A triangulation code of particular relevance here is GEOMPACK, a suite of Fortran 77 codes by Barry Joe, for 2- and 3-dimensional triangulation and convex decomposition problems. In particular, it does both Delaunay triangulation and convex decompositions of polygonal and polyhedral regions, as well as arbitrary-dimensional Delaunay triangulations.   

Notes: Keil and Sack [KS85] given an excellent survey on what is known about partitioning and covering polygons. Expositions on the Hertel-Mehlhorn heuristic [HM83] include [O'R94]. The tex2html_wrap_inline30333 dynamic programming algorithm for minimum convex decomposition using diagonals is due to Keil [Kei85]. The tex2html_wrap_inline30335 algorithm minimizing the number of convex pieces with Steiner points appears in [CD85]. Feng and Pavlidis [FP75b] give a heuristic algorithm for polygon decomposition and apply it to optical character recognition.  

Art gallery problems are an interesting topic related to polygon covering, where we seek to position the minimum number of guards in a given polygon such that every point in the interior of the polygon is watched by at least one guard. This corresponds to covering the polygon with a minimum number of star-shaped polygons. O'Rourke [O'R87] is a beautiful book which presents the art gallery problem and its many variations.     

Related Problems: Triangulation (see page gif), set cover (see page gif).    

next up previous contents index CD CD Algorithms
Next: Simplifying Polygons Up: Computational Geometry Previous: Medial-Axis Transformation

Mon Jun 2 23:33:50 EDT 1997