CGAL::convex_partition_is_valid_2

Definition

Function that determines if a given set of polygons represents a valid convex partitioning for a given sequence of points that represent a simple, counterclockwise-oriented polygon. A convex partition is valid if the polygons do not overlap, the union of the polygons is the same as the original polygon given by the sequence of points, and if each partition polygon is convex.

#include <CGAL/partition_is_valid_2.h>

template<class InputIterator, class ForwardIterator, class Traits>
bool	convex_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 convex partition of the polygon defined by the points in the range [point_first, point_beyond). The function returns true iff the partition is valid and otherwise returns false. Precondition:  The points in the range [point_first, point_beyond) define a simple, counterclockwise-oriented polygon.

Requirements

1. Traits is a model of the concept ConvexPartitionIsValidTraits_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::approx_convex_partition_2
CGAL::greene_approx_convex_partition_2
CGAL::optimal_convex_partition_2
CGAL::partition_is_valid_2
CGAL::is_convex_2

Implementation

This function calls partition_is_valid_2 using the function object Is_convex_2 to determine the convexity of each partition polygon. Thus the time required by this function is O(n log n + e log e) where n is the total number of vertices in the partition polygons and e the total number of edges.

Example

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