CGAL 4.11.3 - 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... | |
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.
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
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::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(nlogn) time for n input points.
#include <CGAL/ch_akl_toussaint.h>
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.
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
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
. 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>
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.
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
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
. 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>
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.
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
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
. 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>
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.
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
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_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(nh) time in the worst case for n input points with h extreme points.
#include <CGAL/ch_jarvis.h>
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.
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
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
. 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>
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.
first
,beyond
) does not contain result
.Requirements
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
. 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>
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>