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

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

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

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

template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator	CGAL::ch_jarvis (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`).

template<class InputIterator , class OutputIterator >
OutputIterator	CGAL::ch_melkman (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`).

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.

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.

Function Documentation

◆ 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

The value type of ForwardIterator and OutputIterator are equivalent to Traits::Point_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.

See also: CGAL::ch_bykat(); CGAL::ch_eddy(); CGAL::ch_graham_andrew(); CGAL::ch_jarvis(); CGAL::ch_melkman(); CGAL::lower_hull_points_2(); CGAL::upper_hull_points_2(); 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

The value type of InputIterator and OutputIterator is equivalent to Traits::Point_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::Compare_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::lower_hull_points_2(); CGAL::upper_hull_points_2(); 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

The value type of InputIterator and OutputIterator is equivalent to Traits::Point_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::Compare_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::lower_hull_points_2(); CGAL::upper_hull_points_2(); 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

The value type of InputIterator and OutputIterator is equivalent to Traits::Point_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_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 ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_jarvis	(	ForwardIterator	first,
		ForwardIterator	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 ForwardIterator is defined.

Requirements

The value type of ForwardIterator and OutputIterator is equivalent to Traits::Point_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::lower_hull_points_2(); CGAL::upper_hull_points_2(); 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	beyond,
		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

The value type of InputIterator and OutputIterator is equivalent to Traits::Point_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::lower_hull_points_2(); CGAL::upper_hull_points_2(); 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 >

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.

◆ convex_hull_2() [2/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

The value type of InputIterator and OutputIterator is equivalent to Traits::Point_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::Compare_signed_distance_to_line_2,
- Traits::Equal_2,
- Traits::Less_xy_2,
- Traits::Less_yx_2,
- Traits::Left_turn_2,
- Traits::Orientation_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.

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.

Functions

Function Documentation

◆ ch_akl_toussaint()

◆ ch_bykat()

◆ ch_eddy()

◆ ch_graham_andrew()

◆ ch_jarvis()

◆ ch_melkman()

◆ convex_hull_2() [1/2]

◆ convex_hull_2() [2/2]