advanced

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.

advanced