User Manual

Author

Susan Hert

Introduction

A partition of a polygon \( P\) is a set of polygons such that the interiors of the polygons do not intersect and the union of the polygons is equal to the interior of the original polygon \( P\). This chapter describes functions for partitioning planar polygons into two types of subpolygons - \( y\)-monotone polygons and convex polygons. The partitions are produced without introducing new (Steiner) vertices.

All the partitioning functions present the same interface to the user. That is, the user provides a pair of input iterators, first and beyond, an output iterator result, and a traits class traits. The points in the range [first, beyond) are assumed to define a simple polygon whose vertices are in counterclockwise order. The computed partition polygons, whose vertices are also oriented counterclockwise, are written to the sequence starting at position result and the past-the-end iterator for the resulting sequence of polygons is returned. The traits classes for the functions specify the types of the input points and output polygons as well as a few other types and function objects that are required by the various algorithms.

Monotone Partitioning

A \( y\)-monotone polygon is a polygon whose vertices \( v_1, \ldots, v_n\) can be divided into two chains \( v_1, \ldots, v_k\) and \( v_k, \ldots, v_n, v_1\), such that any horizontal line intersects either chain at most once. For producing a \( y\)-monotone partition of a given polygon, the sweep-line algorithm presented in [1] is implemented by the function y_monotone_partition_2(). This algorithm runs in \(O(n \log n)\) time and requires \(O(n)\) space. This algorithm does not guarantee a bound on the number of polygons produced with respect to the optimal number.

For checking the validity of the partitions produced by y_monotone_partition_2(), we provide a function is_y_monotone_2(), which determines if a sequence of points in 2D defines a \( y\)-monotone polygon or not. For examples of the use of these functions, see the corresponding reference pages.

Convex Partitioning

Three functions are provided for producing convex partitions of polygons. One produces a partition that is optimal in the number of pieces. The other two functions produce approximately optimal convex partitions. Both these functions produce convex decompositions by first decomposing the polygon into simpler polygons; the first uses a triangulation and the second a monotone partition. These two functions both guarantee that they will produce no more than four times the optimal number of convex pieces but they differ in their runtime complexities. Though the triangulation-based approximation algorithm often results in fewer convex pieces, this is not always the case.

Figure 20.1 Examples of an approximate optimal convex partition (left) and an optimal convex partition (right).

An optimal convex partition can be produced using the function optimal_convex_partition_2().

This function provides an implementation of Greene's dynamic programming algorithm for optimal partitioning [2]. This algorithm requires \(O(n^4)\) time and \(O(n^3)\) space in the worst case.

The function approx_convex_partition_2() implements the simple approximation algorithm of Hertel and Mehlhorn [3] that produces a convex partitioning of a polygon from a triangulation by throwing out unnecessary triangulation edges. The triangulation used in this function is one produced by the 2-dimensional constrained triangulation package of CGAL. For a given triangulation, this convex partitioning algorithm requires \(O(n)\) time and space to construct a decomposition into no more than four times the optimal number of convex pieces.

The sweep-line approximation algorithm of Greene [2], which, given a monotone partition of a polygon, produces a convex partition in \(O(n \log n)\) time and \(O(n)\) space, is implemented by the function greene_approx_convex_partition_2(). The function y_monotone_partition_2() described in Section Monotone Partitioning is used to produce the monotone partition. This algorithm provides the same worst-case approximation guarantee as the algorithm of Hertel and Mehlhorn implemented with approx_convex_partition_2() but can sometimes produce better results (i.e., convex partitions with fewer pieces).

Examples

Examples of the uses of all of the above partition functions are provided with the corresponding reference pages.

In the following we illustrate how to use a property map to enable the trais class to deal with polygons where the vertices are not points. In the example the points are in a vector and the polygons are sequences of indices.

The class Partition_2 has two template parameters, namely a geometric traits class, and a property map to obtain points, in the example by accessing points[i] for the polygon vertex i, and it then performs the predicates required by the concept PartitionTraits_2 on these points.

File Partition_2/y_monotone_partition_indices_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/partition_2.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/property_map.h>
#include <vector>
#include <cassert>
#include <list>
 
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
 
typedef CGAL::Partition_traits_2<K, CGAL::Pointer_property_map<K::Point_2>::type > Partition_traits_2;
 
typedef Partition_traits_2::Point_2                         Point_2;
 
typedef Partition_traits_2::Polygon_2                       Polygon_2;  // a polygon of indices
typedef std::list<Polygon_2>                                Polygon_list;
 
/*
 
      v4     v2
      | \   /|
      |  \ / |
      |  v3  |
      |      |
      v0-----v1
 
 */
 
int main( )
{
  std::vector<K::Point_2> points = { K::Point_2(0,0), K::Point_2(2,0), K::Point_2(2,2), K::Point_2(1,1), K::Point_2(0,2) };
  Partition_traits_2 traits(CGAL::make_property_map(points));
 
 
  Polygon_2 polygon;
  polygon.push_back(0);
  polygon.push_back(1);
  polygon.push_back(2);
  polygon.push_back(3);
  polygon.push_back(4);
 
  Polygon_list partition_polys;
 
  CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                               polygon.vertices_end(),
                               std::back_inserter(partition_polys),
                               traits);
 
   for (const Polygon_2& poly : partition_polys){
     for(Point_2 p : poly.container()){
        std::cout << "points[" << p << "] =  " << points[p] << ", ";
      }
     std::cout << std::endl;
   }
 
   assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     partition_polys.begin(),
                                     partition_polys.end(),
                                     traits));
 
   return 0;
}

In a similar way, the use of an appropriate property map enables to partition faces of a polygonal mesh, or to access points which are a component of a std::tuple.

Implementation History

This package has originally been written by Susan Hert while working at the Max-Planck Institute for Infomatics in Germany. The algorithms have been made free of constructions, and the property map has been added by GeometryFactory for CGAL 5.0.