| advanced |
|
 |
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>
|
| ||||
|
|
| |||
|
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
- Traits is a model of the concept ConvexPartitionIsValidTraits_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.
- 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 logn + e loge) where n is the total number of vertices in the partition polgons 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.
| advanced |
|