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