CGAL 5.0.2 - 2D Convex Hulls and Extreme Points

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

## ◆ ch_akl_toussaint()

template<class ForwardIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::ch_akl_toussaint ( ForwardIterator first, ForwardIterator beyond, OutputIterator result, const Traits & ch_traits = Default_traits() )

#include <CGAL/ch_akl_toussaint.h>

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::Orientation_2,
• Traits::Equal_2.
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.

## ◆ ch_bykat()

template<class InputIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::ch_bykat ( InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits = Default_traits )

#include <CGAL/ch_bykat.h>

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

## ◆ ch_eddy()

template<class InputIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::ch_eddy ( InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits = Default_traits )

#include <CGAL/ch_eddy.h>

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

## ◆ ch_graham_andrew()

template<class InputIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::ch_graham_andrew ( InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits = Default_traits )

#include <CGAL/ch_graham_andrew.h>

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

Examples:
Convex_hull_2/ch_from_cin_to_cout.cpp.

## ◆ ch_jarvis()

template<class InputIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::ch_jarvis ( InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits = Default_traits )

#include <CGAL/ch_jarvis.h>

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

## ◆ ch_melkman()

template<class InputIterator , class OutputIterator >
 OutputIterator CGAL::ch_melkman ( InputIterator first, InputIterator last, OutputIterator result, const Traits & ch_traits = Default_traits )

#include <CGAL/ch_melkman.h>

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

## ◆ convex_hull_2() [1/2]

template<class InputIterator , class OutputIterator , class Traits >
 OutputIterator CGAL::convex_hull_2 ( InputIterator first, InputIterator beyond, OutputIterator result, const Traits & ch_traits )

#include <CGAL/convex_hull_2.h>

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,
• Traits::Orientation_2.
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.

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

## ◆ convex_hull_2() [2/2]

template<class InputIterator , class OutputIterator >
 OutputIterator CGAL::convex_hull_2 ( InputIterator first, InputIterator beyond, OutputIterator result )

#include <CGAL/convex_hull_2.h>

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.