The function lower_hull_points_2 generates the counterclockwise sequence of extreme points on the lower hull of a given set of input points.
generates the counterclockwise sequence of extreme points
on the lower 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 leftmost point;
the rightmost point is not included.
If there is only one extreme point (i.e., leftmost and
rightmost point are equal) the extreme point is reported.
The default traits class Default_traits is the kernel in which the type InputIterator::value_type is defined.
The different treatment by CGAL::upper_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.