Navigation: Up, Table of Contents, Bibliography, Index, Title Page

| advanced |

## CGAL::y_monotone_partition_is_valid_2

### Definition

Function that determines if a given set of polygons represents a valid y-monotone partitioning for a given sequence of points that define a simple, counterclockwise-oriented polygon. A valid partition is one in which the polygons are nonoverlapping and the union of the polygons is the same as the original polygon and each polygon is y-monotone

#include <CGAL/partition_is_valid_2.h>

template<class InputIterator, class ForwardIterator, class Traits>
bool |
y_monotone_partition_is_valid_2 ( | InputIterator point_first, InputIterator point_beyond, ForwardIterator poly_first, ForwardIterator poly_beyond, Traits traits = Default_traits)
|  | determines if the polygons in the range [poly_first, poly_beyond) define a valid y-monotone partition of the polygon represented by the points in the range [point_first, point_beyond). The function returns true iff the partition is valid and otherwise returns false. Precondition: Points in the range [point_first, point_beyond) define a simple, counterclockwise-oriented polygon.

### Requirements

1. Traits is a model of the concept YMonotonePartitionIsValidTraits_2 .
2. InputIterator::value_type should be Traits::Point_2, which should also be the type of the points stored in an object of type Traits::Polygon_2.
3. ForwardIterator::value_type should be 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::y_monotone_partition_2
CGAL::is_y_monotone_2
CGAL::partition_is_valid_2
CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>

### Implementation

This function uses the function partition_is_valid_2 together with the function object Is_y_monotone_2 to determine if each polygon is y-monotone or not. Thus the time required is O(n logn + e loge) where n is the total number of vertices of the partition polygons and e is the total number of edges.

### Example

See the example presented with the function y_monotone_partition_2 for an illustration of the use of this function.

| advanced |

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .