CGAL::ch_graham_andrew
Definition
The function ch_graham_andrew generates the counterclockwise sequence of extreme
points from a given set of input points.
#include <CGAL/ch_graham_andrew.h>
template <class InputIterator, class OutputIterator, class Traits>

OutputIterator

ch_graham_andrew ( 
InputIterator first,
InputIterator beyond,
OutputIterator result,
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.
Precondition:  The source range [first,beyond) does not contain
result. 

The default traits class Default_traits is the kernel in which the
type InputIterator::value_type is defined.
Requirements
 InputIterator::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::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 [And79] and follows the presentation of Mehlhorn
[Meh84]. This algorithm requires $$O(n log$$n) time
in the worst case for $$n input points.