This section describes a function to compute a maximal area -gon that can be inscribed into a given convex polygon . Note that is not unique in general, but it can be chosen in such a way that its vertices form a subset of the vertex set of .
#include <CGAL/extremal_polygon_2.h>
| ||||||
|
|
computes a maximum area inscribed -gon of the convex polygon described by [points_begin, points_end), writes its vertices to o and returns the past-the-end iterator of this sequence.
On compilers not supporting member function templates, the parameter RandomAccessIC is fixed to vector<Point_2>::iterator where Point_2 is the value type of RandomAccessIC.
#include <CGAL/Cartesian.h> #include <CGAL/Point_2.h> #include <CGAL/Polygon_2.h> #include <CGAL/point_generators_2.h> #include <CGAL/random_convex_set_2.h> #include <CGAL/extremal_polygon_2.h> #include <iostream.h> #include <vector.h> int main() { typedef double FT; typedef CGAL_Cartesian< FT > R; typedef CGAL_Point_2< R > Point_2; typedef CGAL_Polygon_traits_2< R > P_traits; typedef vector< Point_2 > Cont; typedef CGAL_Polygon_2< P_traits, Cont > Polygon_2; typedef CGAL_Random_points_in_square_2< Point_2, CGAL_Creator_uniform_2< FT, Point_2 > > Point_generator; Polygon_2 p; int number_of_points( 10); int k( 5); CGAL_random_convex_set_2( number_of_points, back_inserter( p), Point_generator( 1)); cout << "Generated Polygon:\n" << p << endl; Polygon_2 k_gon; CGAL_maximum_area_inscribed_k_gon( p.vertices_begin(), p.vertices_end(), k, back_inserter( k_gon)); cout << "Maximum area " << k << "-gon:\n" << k_gon << endl; }