Computing a Maximum Perimeter Inscribed $k$-gon

This section describes a function to compute a largest perimeter $k$-gon $P$_k that can be inscribed in a given convex polygon $P$. Note that $P$_k is not unique in general, but we know that its vertices form a subset of the vertex set of $P$.

#include <CGAL/extremal_polygon_2.h>

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

computes a maximum perimeter 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 CGAL_Point_2<R> for some representation class R,
2. there is a global function R::FT CGAL_sqrt( R::FT) defined that computes the squareroot of a number,
3. OutputIterator accepts the value type of RandomAccessIC as value type,
4. 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
5. $k\; >=2$.

Note

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.

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.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_perimeter_inscribed_k_gon(
    p.vertices_begin(),
    p.vertices_end(),
    k,
    back_inserter( k_gon));
  cout << "Maximum perimeter " << k << "-gon:\n" << k_gon << endl;

}