CGAL 4.11.3 - 2D Convex Hulls and Extreme Points
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages

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(nlogn) 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(nh) 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(nh) 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(nlogn) 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(nh) 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(nh), where n is the number of input points and h is the number of extreme points. For all other types of iterators, the O(nlogn) 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>