CGAL::extremal_polygon_2

Definition

The function extremal_polygon_2 computes a maximal k-gon that can be inscribed into a given convex polygon. The criterion for maximality and some basic operations have to be specified in an appropriate traits class parameter.

#include <CGAL/extremal_polygon_2.h>

template < class RandomAccessIterator, class OutputIterator, class Traits >
OutputIterator
extremal_polygon_2 (
RandomAccessIterator points_begin,
RandomAccessIterator points_end,
int k,
OutputIterator o,
Traits t)

computes a maximal (as specified by t) 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 t.min_k().

Requirement

  1. Traits is a model for ExtremalPolygonTraits_2.
  2. Value type of RandomAccessIterator is Traits::Point_2.
  3. OutputIterator accepts Traits::Point_2 as value type.

See Also

CGAL::maximum_area_inscribed_k_gon_2
CGAL::maximum_perimeter_inscribed_k_gon_2
ExtremalPolygonTraits_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 log n), where n is the number of vertices in P.