Computing a Maximum Area Inscribed $$k-gon

This section describes a function to compute a maximal area $$k-gon $$P_k that can be inscribed into a given convex polygon $$P. Note that $$P_k 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 $$P.

#include <CGAL/extremal_polygon_2.h>

template < class RandomAccessIC, class OutputIterator >
OutputIterator	maximum_area_inscribed_k_gon ( RandomAccessIC points_begin, RandomAccessIC points_end, int k, OutputIterator o)

computes a maximum area inscribed $$k-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.

Precondition

1. Value type of RandomAccessIC has to be Point_2<R> for some representation class R.
2. OutputIterator accepts the value type of RandomAccessIC as value type,
3. the - at least three - points denoted by the range [points_begin, points_end) form the boundary of a convex polygon (oriented clock- or counterclockwise) and
4. $$k 3.

Note

On compilers not supporting member function templates, the parameter RandomAccessIC is fixed to std::vector<Point_2>::iterator where Point_2 is the value type of RandomAccessIC.

Implementation

Example

#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>
#include <vector>

using namespace std;
using CGAL::random_convex_set_2;
using CGAL::maximum_area_inscribed_k_gon;

typedef double                                FT;
typedef CGAL::Cartesian< FT >                 R;
typedef CGAL::Point_2< R >                    Point;
typedef CGAL::Polygon_traits_2< R >           P_traits;
typedef vector< Point >                       Cont;
typedef CGAL::Polygon_2< P_traits, Cont >     Polygon;
typedef CGAL::Creator_uniform_2< FT, Point >  Creator;
typedef CGAL::Random_points_in_square_2< Point, Creator >
  Point_generator;

int main() {

  Polygon p;
  int number_of_points( 10);
  int k( 5);

  random_convex_set_2( number_of_points,
                       back_inserter( p),
                       Point_generator( 1));
  cout << "Generated Polygon:\n" << p << endl;

  Polygon k_gon;
  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;

  return 0;
}