CGAL 4.7 - 2D Convex Hulls and Extreme Points

## 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.

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.

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.

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.

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.

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.

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.

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>