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
- 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_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 , where is the number of input
points and is the number of extreme points. For all other types of
iterators, the log 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.
