CGAL 4.7 - 2D Convex Hulls and Extreme Points: Extreme Point Functions

\( \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.7 - 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>`