## CGAL::is_y_monotone_2

### Definition

Function for testing the y-monotonicity of a sequence of points.

#include <CGAL/is_y_monotone_2.h>

template<class InputIterator, class Traits>

bool

is_y_monotone_2 ( | InputIterator first, InputIterator beyond, Traits traits)

|  | Determines if the sequence of points in the range [first, beyond) define a y-monotone polygon or not. If so, the function returns true, otherwise it returns false.

### Requirements

1. Traits is a model of the concept IsYMonotoneTraits_2.
2. InputIterator::value_type should be Traits::Point_2.

The default traits class Default_traits is the kernel in which the type InputIterator::value_type is defined.

### See Also

CGAL::Is_y_monotone_2<Traits>
CGAL::y_monotone_partition_2
CGAL::y_monotone_partition_is_valid_2

### Implementation

This function requires O(n) time for a polygon with n vertices.

### Example

The following program computes a y-monotone partitioning of a polygon using the default traits class and stores the partition polygons in the list partition_polys. It then asserts that each of the partition polygons is, in fact, a y-monotone polygon and that the partition is valid. (Note that the assertions are superfluous unless the postcondition checking done by y_monotone_partition_2 has been turned off during compilation.)

    // file: examples/Partition_2/y_monotone_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 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;

    /*
       CGAL::random_polygon_2(50, std::back_inserter(polygon),
                              Point_generator(100));
    */
       make_polygon(polygon);
       CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                    polygon.vertices_end(),
                                    std::back_inserter(partition_polys));

       std::list<Polygon_2>::const_iterator   poly_it;
       for (poly_it = partition_polys.begin(); poly_it != partition_polys.end();
            poly_it++)
       {
          assert(CGAL::is_y_monotone_2((*poly_it).vertices_begin(),
                                       (*poly_it).vertices_end()));
       }

       assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
                                         polygon.vertices_end(),
                                         partition_polys.begin(),
                                         partition_polys.end()));
       return 0;
    }