CGAL::upper_hull_points_2
Definition
The function upper_hull_points_2 generates the counterclockwise sequence of extreme
points on the upper hull of a given set of input points.
#include <CGAL/convex_hull_2.h>
|
template <class InputIterator, class OutputIterator>
|
|
OutputIterator
|
|
upper_hull_points_2 ( |
InputIterator first,
InputIterator beyond,
OutputIterator result,
Traits ch_traits = Default_traits) |
|
| |
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.
| 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::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.
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::lower_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.
