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

1. InputIterator::value_type and OutputIterator::value_type are equilvalent to Traits::Point_2.
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.