CGAL::convex_hull_2

Definition

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

#include <CGAL/convex_hull_2.h>

template <class InputIterator, class OutputIterator>
OutputIterator
convex_hull_2 ( 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 contains 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
CGAL::ch_jarvis
CGAL::ch_melkman

Implementation

One of two algorithms is used, depending on the type of iterator used to specify the input points. For input iterators, the algorithm used is that of Bykat [Byk78], which has a worst-case running time of O(n h), where n is the number of input points and h is the number of extreme points. For all other types of iterators, the O(n logn) algorithm of of Akl and Toussaint [AT78] is used.

Example

In the following example we use the STL-compliant interface of CGAL::Polygon_2 to construct the convex hull polygon from the sequence of extreme points. Point data are read from standard input, the convex hull polygon is shown in a CGAL window. Remember, that when no traits class is specified for the function convex_hull_2, the kernel from which the input points come is used as the default traits class.