Function that determines if a given set of polygons represents a valid partition 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.
#include <CGAL/partition_is_valid_2.h>
template<class InputIterator, class ForwardIterator, class Traits> | ||||
bool |
| |||
returns true iff the polygons in the range [poly_first,
poly_beyond) define a valid partition of the polygon defined by the
points in the range [point_first, point_beyond) and
false otherwise.
Each polygon must also satisfy the property
tested by Traits::Is_valid().
|
The default traits class Default_traits is Partition_traits_2, with the representation type determined by InputIterator::value_type.
CGAL::approx_convex_partition_2
CGAL::greene_approx_convex_partition_2
CGAL::is_y_monotone_2
CGAL::optimal_convex_partition_2
CGAL::Partition_is_valid_traits_2<Traits, PolygonIsValid>
CGAL::y_monotone_partition_2
CGAL::is_convex_2
This function requires O(n log n + e log e + Σi=1p mi) where n is the total number of vertices of the p partition polygons, e is the total number of edges of the partition polygons and mi is the time required by Traits::Is_valid() to test if partition polygon pi is valid.
See the example presented with the function optimal_convex_partition_2 for an illustration of the use of this function.