CGAL 4.14  2D Convex Hulls and Extreme Points

Functions  
template<class BidirectionalIterator , class OutputIterator , class Traits >  
OutputIterator  CGAL::ch_graham_andrew_scan (BidirectionalIterator first, BidirectionalIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits) 
generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line defined by the first and last points in this sequence. More...  
template<class ForwardIterator , class OutputIterator , class Traits >  
OutputIterator  CGAL::ch_jarvis_march (ForwardIterator first, ForwardIterator beyond, const Traits::Point_2 &start_p, const Traits::Point_2 &stop_p, OutputIterator result, const Traits &ch_traits=Default_traits) 
generates the counterclockwise sequence of extreme points from a given set of input points that line between two input points. More...  
template<class InputIterator , class OutputIterator >  
OutputIterator  CGAL::lower_hull_points_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits) 
generates the counterclockwise sequence of extreme points on the lower hull of a given set of input points. More...  
template<class InputIterator , class OutputIterator >  
OutputIterator  CGAL::upper_hull_points_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits) 
generates the counterclockwise sequence of extreme points on the upper hull of a given set of input points. More...  
OutputIterator CGAL::ch_graham_andrew_scan  (  BidirectionalIterator  first, 
BidirectionalIterator  beyond,  
OutputIterator  result,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/ch_graham_andrew.h>
generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line defined by the first and last points in this sequence.
More precisely, it generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line \( pq\) defined by the first ( \(p\)) and last ( \(q\)) points in this sequence ( \( p\) is the value of first
and \( q\) is the value of beyond
\( 1\)). The resulting sequence is placed starting at result
with \( p\); point \( q\) is omitted. The pasttheend iterator for the sequence is returned.
first
,beyond
) contains at least two different points. The points in [first
,beyond
) are sorted with respect to \( pq\), i.e., the sequence of points in [first
,beyond
) define a counterclockwise polygon, for which the GrahamSklanskyprocedure [11] works.The default traits class Default_traits
is the kernel in which the type BidirectionalIterator::value_type
is defined.
Requirements
BidirectionalIterator::value_type
and OutputIterator::value_type
are equivalent to Traits::Point_2
. Traits
defines the following two types from the concept ConvexHullTraits_2
and their corresponding member functions that return instances of these types: Traits::Point_2
, Traits::Left_turn_2
. Implementation
This algorithm requires \( O(n)\) time in the worst case for \( n\) input points.
Example
In the example Convex_hull_2/ch_graham_anderson.cpp, ch_graham_andrew_scan()
is used to realize Anderson's variant [2] of the Graham Scan [7]. The points are sorted counterclockwise around the leftmost point using the Less_rotate_ccw_2
predicate, as defined in the concept ConvexHullTraits_2
. According to the definition of Less_rotate_ccw_2
, the leftmost point is the last point in the sorted sequence and its predecessor on the convex hull is the first point in the sorted sequence. It is not hard to see that the preconditions of ch_graham_andrew_scan()
are satisfied. Anderson's variant of the Graham scan is usually inferior to Andrew's variant because of its higher arithmetic demand.
OutputIterator CGAL::ch_jarvis_march  (  ForwardIterator  first, 
ForwardIterator  beyond,  
const Traits::Point_2 &  start_p,  
const Traits::Point_2 &  stop_p,  
OutputIterator  result,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/ch_jarvis.h>
generates the counterclockwise sequence of extreme points from a given set of input points that line between two input points.
More precisely, it generates the counterclockwise subsequence of extreme points between start_p
and stop_p
of the points in the range [first
,beyond
), starting at position result
with point start_p
. The last point generated is the point preceding stop_p
in the counterclockwise order of extreme points.
The default traits class Default_traits
is the kernel in which the type ForwardIterator::value_type
is defined.
Requirements
ForwardIterator::value_type
and OutputIterator::value_type
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::Equal_2
, Traits::Less_rotate_ccw_2
. Implementation
The 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
start_p
and stop_p
are extreme points with respect to the points in the range [first
,beyond
) and stop_p
is an element of range [first
,beyond
). OutputIterator CGAL::lower_hull_points_2  (  InputIterator  first, 
InputIterator  beyond,  
OutputIterator  result,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/convex_hull_2.h>
generates the counterclockwise sequence of extreme points on the lower hull of a given set of input points.
More precisely, it generates the counterclockwise sequence of extreme points on the lower hull 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. The sequence starts with the leftmost point; the rightmost point is not included. If there is only one extreme point (i.e., leftmost and rightmost point are equal) the extreme point is reported.
first
,beyond
) does not contain result
.The default traits class Default_traits
is the kernel in which the value type of InputIterator
is defined.
The different treatment by upper_hull_points_2()
of the case that all points are equal ensures that concatenation of lower and upper hull points gives the sequence of extreme points.
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::Less_yx_2
, Traits::Left_turn_2
. Implementation
This function uses Andrew's variant of Graham's scan algorithm [3], [9]. The algorithm has worstcase running time of \( O(n \log n)\) for \( n\) input points.
OutputIterator CGAL::upper_hull_points_2  (  InputIterator  first, 
InputIterator  beyond,  
OutputIterator  result,  
const Traits &  ch_traits = Default_traits 

) 
#include <CGAL/convex_hull_2.h>
generates the counterclockwise sequence of extreme points on the upper hull of a given set of input points.
More precisely, it generates the counterclockwise sequence of extreme points on the upper hull 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. The sequence starts with the rightmost point, the leftmost point is not included. If there is only one extreme point (i.e., the leftmost and rightmost point are equal), the extreme point is not reported.
first
,beyond
) does not contain result
.The default traits class Default_traits
is the kernel in which the value type of InputIterator
is defined.
The different treatment by lower_hull_points_2()
of the case that all points are equal ensures that concatenation of lower and upper hull points gives the sequence of extreme points.
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::Less_yx_2
, Traits::Left_turn_2
. Implementation
This function uses Andrew's variant of Graham's scan algorithm [3], [9]. The algorithm has worstcase running time of \( O(n \log n)\) for \( n\) input points.