CGAL 4.10  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 pasttheend 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(n \log n)\) 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 pasttheend 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 nonrecursive 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.
#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 pasttheend 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 twodimensional 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.
#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 pasttheend 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(n \log n)\) 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 pasttheend 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 (giftwrapping) algorithm [8]. This algorithm requires \( O(n h)\) 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 pasttheend 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 pasttheend 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 worstcase 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.
#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>