The function upper_hull_points_2 generates the counterclockwise sequence of extreme points on the upper hull of a given set of input points.
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 past-the-end 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.
The default traits class Default_traits is the kernel in which the type InputIterator::value_type is defined.
The different treatment by CGAL::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.
This function uses Andrew's variant of Graham's scan algorithm [And79, Meh84]. The algorithm has worst-case running time of log for input points.