## CGAL::greene_approx_convex_partition_2

### Definition

Function that produces a set of convex polygons that represent a partitioning of a polygon defined on a sequence of points. The number of convex polygons produced is no more than four times the minimal number.

#include <CGAL/partition_2.h>

template <class InputIterator, class OutputIterator, class Traits>

OutputIterator

greene_approx_convex_partition_2 ( | InputIterator first, InputIterator beyond, OutputIterator result, Traits traits = Default_traits)

computes a partition of the polygon defined by the points in the range [first, beyond) into convex polygons. The counterclockwise-oriented partition polygons are written to the sequence starting at position result. The past-the-end iterator for the resulting sequence of polygons is returned.
Precondition: The points in the range [first, beyond) define a simple, counterclockwise-oriented polygon.

### Requirements

1. Traits is a model of the concepts PartitionTraits_2 and YMonotonePartitionTraits_2. For the purpose of checking the validity of the y-monotone partition produced as a preprocessing step for the convex partitioning, it must also be a model of YMonotonePartitionIsValidTraits_2. For the purpose of checking the postcondition that the convex partition is valid, Traits must also be a model of ConvexPartitionIsValidTraits_2.
2. OutputIterator::value_type is equivalent to Traits::Polygon_2.
3. InputIterator::value_type is equivalent to Traits::Point_2, which should also be equivalent to the type of the points stored in an object of type Traits::Polygon_2.

The default traits class Default_traits is Partition_traits_2, with the representation type determined by InputIterator::value_type.

### See Also

CGAL::approx_convex_partition_2
CGAL::convex_partition_is_valid_2
CGAL::optimal_convex_partition_2
CGAL::partition_is_valid_2
CGAL::y_monotone_partition_2

### Implementation

This function implements the the approximation algorithm of Greene [Gre83] and requires O(n logn) time and O(n) space to produce a convex partitioning given a y-monotone partitioning of a polygon with n vertices. The function y_monotone_partition_2 is used to produce the monotone partition.

### Example

The following program computes an approximately optimal convex partitioning of a polygon using the default traits class and stores the partition polygons in the list partition_polys.

    // file: examples/Partition_2/greene_approx_convex_ex.C

    #include <CGAL/basic.h>
    #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
    #include <CGAL/Partition_traits_2.h>
    #include <CGAL/partition_2.h>
    #include <CGAL/point_generators_2.h>
    #include <CGAL/random_polygon_2.h>
    #include <cassert>
    #include <list>

    typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
    typedef CGAL::Partition_traits_2<K>                         Traits;
    typedef Traits::Point_2                                     Point_2;
    typedef Traits::Polygon_2                                   Polygon_2;
    typedef Polygon_2::Vertex_iterator                          Vertex_iterator;
    typedef std::list<Polygon_2>                                Polygon_list;
    typedef CGAL::Creator_uniform_2<int, Point_2>               Creator;
    typedef CGAL::Random_points_in_square_2< Point_2, Creator > Point_generator;

    void make_polygon(Polygon_2& polygon)
    {
       polygon.push_back(Point_2(391, 374));
       polygon.push_back(Point_2(240, 431));
       polygon.push_back(Point_2(252, 340));
       polygon.push_back(Point_2(374, 320));
       polygon.push_back(Point_2(289, 214));
       polygon.push_back(Point_2(134, 390));
       polygon.push_back(Point_2( 68, 186));
       polygon.push_back(Point_2(154, 259));
       polygon.push_back(Point_2(161, 107));
       polygon.push_back(Point_2(435, 108));
       polygon.push_back(Point_2(208, 148));
       polygon.push_back(Point_2(295, 160));
       polygon.push_back(Point_2(421, 212));
       polygon.push_back(Point_2(441, 303));
    }

    int main()
    {
       Polygon_2    polygon;
       Polygon_list partition_polys;
       Traits       partition_traits;

    /*
       CGAL::random_polygon_2(50, std::back_inserter(polygon),
                              Point_generator(100));
    */
       make_polygon(polygon);
       CGAL::greene_approx_convex_partition_2(polygon.vertices_begin(),
                                              polygon.vertices_end(),
                                              std::back_inserter(partition_polys),
                                              partition_traits);
       assert(CGAL::convex_partition_is_valid_2(polygon.vertices_begin(),
                                                polygon.vertices_end(),
                                                partition_polys.begin(),
                                                partition_polys.end(),
                                                partition_traits));
       return 0;
    }