CGAL::ch_melkman
Definition
The function ch_melkman computes the counterclockwise sequence of
extreme points of a sequence of points that forms a simple polyline or polygon.
#include <CGAL/ch_melkman.h>
template <class InputIterator, class OutputIterator>

OutputIterator

ch_melkman ( 
InputIterator first,
InputIterator last,
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.
Precondition:  The source range [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
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::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
CGAL::convex_hull_2
Implementation
It uses an implementation of Melkman's algorithm [Mel87]. Running
time of this is linear.