Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## 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

1. InputIterator::value_type and OutputIterator::value_type are equivalent 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::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 logn) for n input points.

Next: upper_hull_points_2

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .