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:

• Should all the pieces be triangles? - The mother of all polygon partitioning problems is triangulation, where the interior of the polygon is completely partitioned into triangles. Triangles are always convex and have only three sides, so any geometric operation performed on a triangle is destined to be as simple as it can be.  

  Because triangles all have three sides, all triangulations of polygons contain exactly the same number of pieces. Therefore, triangulation cannot be the answer if we seek a small number of convex pieces. The goal of finding ``nice'' triangulations revolves around the shape of the triangles. See Section for a thorough discussion of triangulation.

• Do I want to cover or partition my polygon? - Partitioning a polygon means completely dividing the interior into nonoverlapping pieces. Covering a polygon means that our decomposition is permitted to contain mutually overlapping pieces. Both can be useful in different situations. In decomposing a complicated query polygon in preparation for range search (Section ), we seek a partitioning, so that each point we locate occurs in exactly one piece. In decomposing a polygon for painting purposes, a covering suffices, since there is no difficulty with filling in a region twice. We will concentrate here on partitioning, since it is simpler to do right, and any application needing a covering will accept a partitioning. The only potential drawback is that partitions can be somewhat larger than coverings.    
• Am I allowed to add extra vertices? - A final issue associated with polygon decomposition is whether we are allowed to add Steiner vertices (either by splitting edges or adding interior points) or whether we are restricted to adding chords between two existing vertices. The former may result in a smaller number of pieces, at the cost of more complicated algorithms and perhaps messier results.  

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 subpolygons split by a chord, runs in . Faster algorithms use fancier data structures, running in time, where r is the number of reflex vertices. An 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 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 dynamic programming algorithm for minimum convex decomposition using diagonals is due to Keil [Kei85]. The 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 ), set cover (see page ).