CGAL::lower_hull_points_2
Definition
The function lower_hull_points_2 generates the counterclockwise sequence of extreme
points on the lower hull of a given set of input points.
#include <CGAL/convex_hull_2.h>
|
template <class InputIterator, class OutputIterator>
|
|
OutputIterator
|
|
lower_hull_points_2 ( |
InputIterator first,
InputIterator beyond,
OutputIterator result,
Traits ch_traits = Default_traits) |
|
| |
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.
| 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.
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.
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_graham_andrew
CGAL::ch_graham_andrew_scan
CGAL::upper_hull_points_2
Implementation
This function uses Andrew's variant of Graham's scan algorithm
[And79, Meh84]. The algorithm has worst-case running time
of O(n log n) for n input points.
