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

OutputIterator

convex_hull_2 ( 
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 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.
See Also
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 [Byk78], 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
[AT78] is used.
Example
In the following example we use the STLcompliant interface of
CGAL::Polygon_2 to construct the convex hull polygon from the
sequence of extreme points. Point data are read from standard input, the
convex hull polygon is shown in a CGAL window.
Remember, that when no traits class is specified for the function
convex_hull_2, the kernel from which the input points come is
used as the default traits class.