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

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

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

◆ 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_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 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::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

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

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

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

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]