CGAL::maximum_area_inscribed_k_gon_2

Definition

The function maximum_area_inscribed_k_gon_2 computes a maximum area k-gon Pk that can be inscribed into a given convex polygon P. Note that

#include <CGAL/extremal_polygon_2.h>

template < class RandomAccessIterator, class OutputIterator >
OutputIterator
maximum_area_inscribed_k_gon_2 (
RandomAccessIterator points_begin,
RandomAccessIterator 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. the - at least three - points denoted by the range [points_begin, points_end) form the boundary of a convex polygon (oriented clock- or counterclockwise).
  2. k greater or equal 3.

Requirement

  1. Value type of RandomAccessIterator is K::Point_2 where K is a model for Kernel.
  2. OutputIterator accepts the value type of RandomAccessIterator as value type.

See Also

CGAL::maximum_perimeter_inscribed_k_gon_2
ExtremalPolygonTraits_2
CGAL::Extremal_polygon_area_traits_2<K>
CGAL::Extremal_polygon_perimeter_traits_2<K>
CGAL::extremal_polygon_2
CGAL::monotone_matrix_search

Implementation

The implementation uses monotone matrix search [AKM+87] and has a worst case running time of O(k · n + n · logn), where n is the number of vertices in P.

Example

The following code generates a random convex polygon p with ten vertices and computes the maximum area inscribed five-gon of p.

File: examples/Matrix_search/extremal_polygon_2_area.cpp
#include <CGAL/Cartesian.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>

typedef double                                    FT;

struct Kernel : public CGAL::Cartesian<FT> {};

typedef Kernel::Point_2                           Point;
typedef std::vector<int>                          Index_cont;
typedef CGAL::Polygon_2<Kernel>                   Polygon_2;
typedef CGAL::Random_points_in_square_2<Point>    Generator;

int main() {

  int n = 10;
  int k = 5;

  // generate random convex polygon:
  Polygon_2 p;
  CGAL::random_convex_set_2(n, std::back_inserter(p), Generator(1));
  std::cout << "Generated Polygon:\n" << p << std::endl;

  // compute maximum area incribed k-gon of p:
  Polygon_2 k_gon;
  CGAL::maximum_area_inscribed_k_gon_2(
    p.vertices_begin(), p.vertices_end(), k, std::back_inserter(k_gon));
  std::cout << "Maximum area " << k << "-gon:\n"
            << k_gon << std::endl;

  return 0;
}