\( \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.5 - 2D Convex Hulls and Extreme Points
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Functions
Extreme Point Functions
2D Convex Hulls and Extreme Points Reference

Functions

template<class ForwardIterator >
void CGAL::ch_e_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &e, const Traits &ch_traits=Default_traits)
 The function ch_e_point() finds a point of a given set of input points with maximal \( x\) coordinate. More...
 
template<class ForwardIterator >
void CGAL::ch_n_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &n, const Traits &ch_traits=Default_traits)
 The function ch_n_point() finds a point in a given set of input points with maximal \( y\) coordinate. More...
 
template<class ForwardIterator >
void CGAL::ch_ns_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &n, ForwardIterator &s, const Traits &ch_traits=Default_traits)
 The function ch_ns_point() finds the points of a given set of input points with minimal and maximal \( x\) coordinates. More...
 
template<class ForwardIterator >
void CGAL::ch_nswe_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &n, ForwardIterator &s, ForwardIterator &w, ForwardIterator &e, const Traits &ch_traits=Default_traits)
 The function ch_nswe_point() finds the four extreme points of a given set of input points using a linear scan of the input points. More...
 
template<class ForwardIterator >
void CGAL::ch_s_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &s, const Traits &ch_traits=Default_traits)
 The function ch_s_point() finds a points in a given set of input points with minimal \( y\) coordinates. More...
 
template<class ForwardIterator >
void CGAL::ch_we_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &w, ForwardIterator &e, const Traits &ch_traits=Default_traits)
 The function ch_we_point() finds two points of a given set of input points with minimal and maximal \( x\) coordinates. More...
 
template<class ForwardIterator >
void CGAL::ch_w_point (ForwardIterator first, ForwardIterator beyond, ForwardIterator &w, const Traits &ch_traits=Default_traits)
 The function ch_w_point() finds a point in a given set of input points with minimal \( x\) coordinate. More...
 

Function Documentation

template<class ForwardIterator >
void CGAL::ch_e_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  e,
const Traits &  ch_traits = Default_traits 
)

The function ch_e_point() finds a point of a given set of input points with maximal \( x\) coordinate.

It traverses the range [first,beyond). After execution, the value of e is an iterator in the range such that *e \( \ge_{xy}\) *it for all iterators it in the range.

The default traits class Default_traits is the kernel in which the value type of ForwardIterator is defined.

Requirements

Traits defines a type Traits::Less_xy_2 as described in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

See Also
CGAL::ch_nswe_point()
CGAL::ch_n_point()
CGAL::ch_ns_point()
CGAL::ch_s_point()
CGAL::ch_w_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_n_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  n,
const Traits &  ch_traits = Default_traits 
)

The function ch_n_point() finds a point in a given set of input points with maximal \( y\) coordinate.

It traverses the range [first,beyond). After execution, the value of n is an iterator in the range such that *n \( \ge_{yx}\) *it for all iterators it in the range.

The default traits class Default_traits is the kernel in which the type ForwardIterator::value_type is defined.

Requirements

Traits defines the type Traits::Less_yx_2 as specified in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

See Also
CGAL::ch_e_point()
CGAL::ch_nswe_point()
CGAL::ch_ns_point()
CGAL::ch_s_point()
CGAL::ch_w_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_ns_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  n,
ForwardIterator &  s,
const Traits &  ch_traits = Default_traits 
)

The function ch_ns_point() finds the points of a given set of input points with minimal and maximal \( x\) coordinates.

It traverses the range [first,beyond). After execution, the value of n is an iterator in the range such that *n \( \ge_{yx}\) *it for all iterators it in the range. Similarly, for s the inequality *s \( \le_{yx}\) *it holds for all iterators in the range.

The default traits class Default_traits is the kernel in which the value type of ForwardIterator is defined.

Requirements

Traits defines the type Traits::Less_yx_2 as specified in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

See Also
CGAL::ch_e_point()
CGAL::ch_nswe_point()
CGAL::ch_n_point()
CGAL::ch_s_point()
CGAL::ch_w_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_nswe_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  n,
ForwardIterator &  s,
ForwardIterator &  w,
ForwardIterator &  e,
const Traits &  ch_traits = Default_traits 
)

The function ch_nswe_point() finds the four extreme points of a given set of input points using a linear scan of the input points.

That is, it determines the points with maximal \( y\), minimal \( y\), minimal \( x\), and maximal \( x\) coordinates.

It traverses the range [first,beyond). After execution, the value of n is an iterator in the range such that *n \( \ge_{yx}\) *it for all iterators it in the range. Similarly, for s, w, and e the inequalities *s \( \le_{yx}\) *it, *w \( \le_{xy}\) *it, and *e \( \ge_{xy}\) *it hold for all iterators it in the range.

Requirements

Traits contains the following subset of types from the concept ConvexHullTraits_2 and their corresponding member functions that return instances of these types:

  • Traits::Less_xy_2,
  • Traits::Less_yx_2.

The default traits class Default_traits is the kernel in which the type ForwardIterator::value_type is defined.

See Also
CGAL::ch_e_point()
CGAL::ch_n_point()
CGAL::ch_ns_point()
CGAL::ch_s_point()
CGAL::ch_w_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_s_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  s,
const Traits &  ch_traits = Default_traits 
)

The function ch_s_point() finds a points in a given set of input points with minimal \( y\) coordinates.

It traverses the range [first,beyond). After execution, the value of s is an iterator in the range such that *s \( \le_{yx}\) *it for all iterators it in the range.

The default traits class Default_traits is the kernel in which the type ForwardIterator::value_type is defined.

Requirements

Traits defines the type Traits::Less_yx_2 as specified in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

See Also
CGAL::ch_e_point()
CGAL::ch_nswe_point()
CGAL::ch_n_point()
CGAL::ch_ns_point()
CGAL::ch_w_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_w_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  w,
const Traits &  ch_traits = Default_traits 
)

The function ch_w_point() finds a point in a given set of input points with minimal \( x\) coordinate.

It traverses the range [first,beyond). After execution, the value of w is an iterator in the range such that *w \( \le_{xy}\) *it for all iterators it in the range.

Requirements

Traits defines the type Traits::Less_xy_2 as specified in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

The default traits class Default_traits is the kernel in which the type ForwardIterator::value_type is defined.

See Also
CGAL::ch_e_point()
CGAL::ch_nswe_point()
CGAL::ch_n_point()
CGAL::ch_ns_point()
CGAL::ch_s_point()
CGAL::ch_we_point()

#include <CGAL/ch_selected_extreme_points_2.h>

template<class ForwardIterator >
void CGAL::ch_we_point ( ForwardIterator  first,
ForwardIterator  beyond,
ForwardIterator &  w,
ForwardIterator &  e,
const Traits &  ch_traits = Default_traits 
)

The function ch_we_point() finds two points of a given set of input points with minimal and maximal \( x\) coordinates.

It traverses the range [first,beyond). After execution, the value of w is an iterator in the range such that *w \( \le_{xy}\) *it for all iterators it in the range. Similarly, for e the inequality *e \( \ge_{xy}\) *it holds for all iterators in the range.

The default traits class Default_traits is the kernel in which the type ForwardIterator::value_type is defined.

Requirements

Traits defines the type Traits::Less_xy_2 as specified in the concept ConvexHullTraits_2 and the corresponding member function that returns an instance of this type.

See Also
CGAL::ch_e_point()
CGAL::ch_nswe_point()
CGAL::ch_n_point()
CGAL::ch_ns_point()
CGAL::ch_s_point()
CGAL::ch_w_point()

#include <CGAL/ch_selected_extreme_points_2.h>