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
- the - at least three - points denoted by the range
[points_begin, points_end) form the boundary of a
convex polygon (oriented clock- or counterclockwise).
- k ≥ t.min_k().
Requirement
- Traits is a model for ExtremalPolygonTraits_2.
- Value type of RandomAccessIterator is Traits::Point_2.
- 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.
