Navigation: Up, Table of Contents,  Package Overview,  Bibliography,  Index,  Title Page , Acknowledging CGAL

CGAL::ch_graham_andrew

Definition

The function ch_graham_andrew generates the counterclockwise sequence of extreme points from a given set of input points.

#include <CGAL/ch_graham_andrew.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator
ch_graham_andrew ( InputIterator first,
InputIterator beyond,
OutputIterator result,
Traits ch_traits = Default_traits)
generates the counterclockwise sequence of extreme points 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. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence.
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.

Requirements

  1. InputIterator::value_type and OutputIterator::value_type are equivalent to Traits::Point_2.
  2. Traits defines the following subset of types from the concept ConvexHullTraits_2 and their corresponding member functions that return instances of these types:

See Also

CGAL::ch_akl_toussaint
CGAL::ch_bykat
CGAL::ch_eddy
CGAL::ch_graham_andrew_scan
CGAL::ch_jarvis
CGAL::ch_melkman
CGAL::convex_hull_2
CGAL::lower_hull_points_2
CGAL::upper_hull_points_2

Implementation

This function implements Andrew's variant of the Graham scan algorithm [And79] and follows the presentation of Mehlhorn [Meh84]. This algorithm requires O(n logn) time in the worst case for n input points.

Next: ch_graham_andrew_scan
Navigation: Up, Table of Contents,  Package Overview,  Bibliography,  Index,  Title Page , Acknowledging CGAL
CGAL Open Source Project. Release 3.3.1. 25 August 2007.