The function ch_graham_andrew_scan generates the counterclockwise sequence of extreme points from a given set of input points that are not left of the line defined by the first and last points in this sequence.
#include <CGAL/ch_graham_andrew.h>
 

 
generates the counterclockwise sequence of extreme points that are
not left of $$pq, where $$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. Precondition: The range [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 [Skl72] works. 
The default traits class Default_traits is the kernel in which the type BidirectionalIterator::value_type is defined.
CGAL::ch_graham_andrew
CGAL::lower_hull_points_2
CGAL::upper_hull_points_2
The function uses Andrew's variant of the Graham scan algorithm [And79] . This algorithm requires $$O(n log$$n) time in the worst case for $$n input points.
In the following example ch_graham_andrew_scan() is used to realize Anderson's variant [And78] of the Graham Scan [Gra72]. 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.
template <class InputIterator, class OutputIterator, class Traits> OutputIterator ch_graham_anderson( InputIterator first, InputIterator beyond, OutputIterator result, const Traits& ch_traits) { typedef typename Traits::Less_xy_2 Less_xy_2; typedef typename Traits::Point_2 Point_2; typedef typename Traits::Less_rotate_ccw_2 Less_rotate_ccw_2; if (first == beyond) return result; std::vector< Point_2 > V; copy( first, beyond, back_inserter(V) ); typename std::vector< Point_2 >::iterator it = std::min_element(V.begin(), V.end(), Less_xy_2()); std::sort( V.begin(), V.end(), Less_rotate_ccw_2(*it) ); if ( *(V.begin()) == *(V.rbegin()) ) { *result = *(V.begin()); ++result; return result; } return ch_graham_andrew_scan( V.begin(), V.end(), result, ch_traits); }