Loading [MathJax]/extensions/TeX/newcommand.js
\newcommand{\E}{\mathrm{E}} \newcommand{\A}{\mathrm{A}} \newcommand{\R}{\mathrm{R}} \newcommand{\N}{\mathrm{N}} \newcommand{\Q}{\mathrm{Q}} \newcommand{\Z}{\mathrm{Z}} \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }
CGAL 4.12 - Inscribed Areas
All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Modules Pages
ExtremalPolygonTraits_2 Concept Reference

Definition

Advanced

The concept ExtremalPolygonTraits_2 provides the types and operations needed to compute a maximal k-gon that can be inscribed into a given convex polygon.

Note
ExtremalPolygonTraits_2::Less_xy_2 and ExtremalPolygonTraits_2::Orientation_2 are used for (expensive) precondition checking only. Therefore, they need not to be specified, in case that precondition checking is disabled.
Has Models:

CGAL::Extremal_polygon_area_traits_2<K>

CGAL::Extremal_polygon_perimeter_traits_2<K>

See also
CGAL::maximum_area_inscribed_k_gon_2()
CGAL::maximum_perimeter_inscribed_k_gon_2()
CGAL::extremal_polygon_2()

Types

typedef unspecified_type FT
 model for FieldNumberType.
 
typedef unspecified_type Point_2
 model for Kernel::Point_2.
 
typedef unspecified_type Less_xy_2
 model for Kernel::Less_xy_2.
 
typedef unspecified_type Orientation_2
 model for Kernel::Orientation_2.
 
typedef unspecified_type Operation
 AdaptableBinaryFunction class op: Point_2 \times Point_2 \rightarrow FT. More...
 

Operations

int min_k () const
 returns the minimal k for which a maximal k-gon can be computed. More...
 
FT init (const Point_2 &p, const Point_2 &q) const
 returns the value of the objective function for a polygon consisting of the two points p and q. More...
 
Operation operation (const Point_2 &p) const
 return Operation where p is the fixed root point.
 
template<class RandomAccessIterator , class OutputIterator >
OutputIterator compute_min_k_gon (RandomAccessIterator points_begin, RandomAccessIterator points_end, FT &max_area, OutputIterator o) const
 writes the points of [points_begin, points_end) forming a min_k()-gon rooted at points_begin[0] of maximal value to o and returns the past-the-end iterator for that sequence (== o + min_k()).
 
Less_xy_2 less_xy_2_object ()
 
Orientation_2 orientation_2_object ()
 

Member Typedef Documentation

◆ Operation

AdaptableBinaryFunction class op: Point_2 \times Point_2 \rightarrow FT.

Together with init this operation recursively defines the objective function to maximize. Let p and q be two vertices of a polygon P such that q precedes p in the oriented vertex chain of P starting with vertex root. Then op(p,q) returns the value by which an arbitrary sub-polygon of P with vertices from [root,\, q] increases when p is added to it. E.g. in the maximum area case this is the area of the triangle (root,\, q,\, p).

Member Function Documentation

◆ init()

FT ExtremalPolygonTraits_2::init ( const Point_2 p,
const Point_2 q 
) const

returns the value of the objective function for a polygon consisting of the two points p and q.

(e.g. in the maximum area case this is FT( 0).)

◆ min_k()

int ExtremalPolygonTraits_2::min_k ( ) const

returns the minimal k for which a maximal k-gon can be computed.

(e.g. in the maximum area case this is three.)