CGAL::greene_approx_convex_partition_2
Definition
Function that produces a set of
convex polygons that represent a partitioning of a polygon defined
on a sequence of points.
The number of convex polygons produced is
no more than four times the minimal number.
#include <CGAL/partition_2.h>
template <class InputIterator, class OutputIterator, class Traits>
|
OutputIterator
|
greene_approx_convex_partition_2 ( |
InputIterator first,
InputIterator beyond,
OutputIterator result,
Traits traits = Default_traits) |
|
| |
computes a partition of the polygon defined
by the points in the range [first, beyond) into convex
polygons. The counterclockwise-oriented partition polygons are written to
the sequence starting at position result. The past-the-end iterator for
the resulting sequence of polygons is returned.
Precondition: | The points in the range [first, beyond) define a simple,
counterclockwise-oriented polygon. |
|
Requirements
- Traits is a model of the concepts PartitionTraits_2
and YMonotonePartitionTraits_2.
For the purpose of
checking the validity of the -monotone partition produced as
a preprocessing step for the convex partitioning, it must also
be a model of YMonotonePartitionIsValidTraits_2.
For the purpose of checking
the postcondition that the convex partition is valid, Traits
must also be a model of ConvexPartitionIsValidTraits_2.
- OutputIterator::value_type is equivalent to
Traits::Polygon_2.
- InputIterator::value_type is equivalent to
Traits::Point_2,
which should also be equivalent to the type of the points stored in
an object of type 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::convex_partition_is_valid_2
CGAL::optimal_convex_partition_2
CGAL::partition_is_valid_2
CGAL::y_monotone_partition_2
Implementation
This function implements the approximation algorithm of
Greene [Gre83] and requires log time and space
to produce a convex partitioning given a -monotone partitioning of a
polygon with vertices. The function y_monotone_partition_2
is used to produce the monotone partition.
Example
The following program computes an approximately optimal
convex partitioning of a polygon using the default
traits class and stores the partition polygons in the list
partition_polys.
File: examples/Partition_2/greene_approx_convex_partition_2.cpp
#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 Polygon_2::Vertex_iterator Vertex_iterator;
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;
Traits partition_traits;
/*
CGAL::random_polygon_2(50, std::back_inserter(polygon),
Point_generator(100));
*/
make_polygon(polygon);
CGAL::greene_approx_convex_partition_2(polygon.vertices_begin(),
polygon.vertices_end(),
std::back_inserter(partition_polys),
partition_traits);
assert(CGAL::convex_partition_is_valid_2(polygon.vertices_begin(),
polygon.vertices_end(),
partition_polys.begin(),
partition_polys.end(),
partition_traits));
return 0;
}