CGAL 4.7 - 2D Convex Hulls and Extreme Points: Convex Hull 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
Convex Hull Functions
2D Convex Hulls and Extreme Points Reference

##

## Functions

template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_akl_toussaint (ForwardIterator first, ForwardIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits())
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). More...
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_bykat (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). More...
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_eddy (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). More...
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_graham_andrew (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). More...
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_jarvis (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). More...
template<class InputIterator , class OutputIterator >
OutputIterator | CGAL::ch_melkman (InputIterator first, InputIterator last, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`, `beyond`). More...
template<class InputIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::convex_hull_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`) with a user provided traits class. More...
template<class InputIterator , class OutputIterator >
OutputIterator | CGAL::convex_hull_2 (InputIterator first, InputIterator beyond, OutputIterator result)
| generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`) using as traits class the kernel in which the point type is defined. More...

## Function Documentation

template<class ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_akl_toussaint | ( | ForwardIterator | first,
|  | ForwardIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits()`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`. The default traits class `Default_traits` is the kernel in which the value type of `ForwardIterator` is defined.

Requirements

1. The value type of `ForwardIterator` and `OutputIterator` are equivalent to `Traits::Point_2`.
2. `Traits` defines the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Less_xy_2`,
   - `Traits::Less_yx_2`,
   - `Traits::Left_turn_2`,
   - `Traits::Equal_2`.

See Also
  `CGAL::ch_bykat()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`

Implementation

This function uses the algorithm of Akl and Toussaint [1] that requires \( O(n \log n)\) time for \( n\) input points.

`#include <CGAL/ch_akl_toussaint.h>`

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_bykat | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

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

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` defines the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Less_signed_distance_to_line_2`,
   - `Traits::Left_turn_2`,
   - `Traits::Less_xy_2`,
   - `Traits::Equal_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`

Implementation

This function implements the non-recursive variation of Eddy's algorithm [6] described in [5]. This algorithm requires \( O(n h)\) time in the worst case for \( n\) input points with \( h\) extreme points.

`#include <CGAL/ch_bykat.h>`

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_eddy | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

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

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` defines the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Equal_2`,
   - `Traits::Less_signed_distance_to_line_2`,
   - `Traits::Left_turn_2`,
   - `Traits::Less_xy_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_bykat()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`

Implementation

This function implements Eddy's algorithm [6], which is the two-dimensional version of the quickhull algorithm [4].

This algorithm requires \( O(n h)\) time in the worst case for \( n\) input points with \( h\) extreme points.

`#include <CGAL/ch_eddy.h>`

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_graham_andrew | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

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

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` defines the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Less_xy_2`,
   - `Traits::Left_turn_2`,
   - `Traits::Equal_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_bykat()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew_scan()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`
  `CGAL::lower_hull_points_2()`
  `CGAL::upper_hull_points_2()`

Implementation

This function implements Andrew's variant of the Graham scan algorithm [3] and follows the presentation of Mehlhorn [9]. This algorithm requires \( O(n \log n)\) time in the worst case for \( n\) input points.

`#include <CGAL/ch_graham_andrew.h>`

Examples:
  Convex_hull_2/ch_from_cin_to_cout.cpp.

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_jarvis | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

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

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` defines the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Equal_2`,
   - `Traits::Less_rotate_ccw_2`,
   - `Traits::Less_xy_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_bykat()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis_march()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`

Implementation

This function uses the Jarvis march (gift-wrapping) algorithm [8]. This algorithm requires \( O(n h)\) time in the worst case for \( n\) input points with \( h\) extreme points.

`#include <CGAL/ch_jarvis.h>`

template<class InputIterator , class OutputIterator >

OutputIterator CGAL::ch_melkman | ( | InputIterator | first,
|  | InputIterator | last,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`, `beyond`).

The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned.

Precondition
  The source range [`first`,`beyond`) corresponds to a simple polyline. [`first`,`beyond`) does not contain `result`.

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

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` contains the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Equal_2`,
   - `Traits::Less_xy_2`,
   - `Traits::Left_turn_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_bykat()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`
  `CGAL::convex_hull_2()`

Implementation

It uses an implementation of Melkman's algorithm [10]. Running time of this is linear.

`#include <CGAL/ch_melkman.h>`

template<class InputIterator , class OutputIterator , class Traits >

OutputIterator CGAL::convex_hull_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`) with a user provided traits class.

It generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`). The resulting sequence is placed starting at position `result`, and the past-the-end iterator for the resulting sequence is returned. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` contains the following subset of types from the concept `ConvexHullTraits_2` and their corresponding member functions that return instances of these types:
   - `Traits::Point_2`,
   - `Traits::Less_signed_distance_to_line_2`,
   - `Traits::Equal_2`,
   - `Traits::Less_xy_2`,
   - `Traits::Less_yx_2`,
   - `Traits::Left_turn_2`.

See Also
  `CGAL::ch_akl_toussaint()`
  `CGAL::ch_bykat()`
  `CGAL::ch_eddy()`
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_jarvis()`
  `CGAL::ch_melkman()`

Implementation

One of two algorithms is used, depending on the type of iterator used to specify the input points. For input iterators, the algorithm used is that of Bykat [5], which has a worst-case running time of \( O(n h)\), where \( n\) is the number of input points and \( h\) is the number of extreme points. For all other types of iterators, the \( O(n \log n)\) algorithm of of Akl and Toussaint [1] is used.

`#include <CGAL/convex_hull_2.h>`

Examples:
  Convex_hull_2/array_convex_hull_2.cpp, Convex_hull_2/iostream_convex_hull_2.cpp, and Convex_hull_2/vector_convex_hull_2.cpp.

template<class InputIterator , class OutputIterator >

OutputIterator CGAL::convex_hull_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result
| ) |  |

generates the counterclockwise sequence of extreme points of the points in the range [`first`,`beyond`) using as traits class the kernel in which the point type is defined.

The kernel is deduced using `std::iterator_traits` and `CGAL::Kernel_traits`.

`#include <CGAL/convex_hull_2.h>`