CGAL provides functions computing the counterclockwise sequence of extreme points for a set of points, i.e. the counterclockwise sequence of points on the convex hull of the set of points. Furthermore, functions computing special extreme points are provided. Finally, there are functions that check whether a given sequence of points forms a (counter)clockwise convex polygon.
The last parameter Traits in the convex hull and extreme point functions is a traits class that defines the primitives that are used in the algorithms. For example Traits::Point_2 is a mapping on a point class.
CGAL provides implementations of convex hull traits classes as
described in . A default
implementation CGAL_convex_hull_traits_2<R> is provided
for the two-dimensional CGAL kernel.
This traits class is used in default versions of the functions that do not
have a traits class parameter. Such default versions exists for all the
functions specified below.
Own convex hull traits classes can be designed according to the
requirements for such traits classes listed in
.
See also Section 2 of the Reference Manual Part 0, General Introduction.
#include <CGAL/convex_hull_2.h>
| ||||
|
| |||
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. TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn. |
Besides the default algorithm for computing convex hulls, implementations
of some classical convex hull algorithms are available, with the same semantics
as the default algorithm.
#include <CGAL/ch_akl_toussaint.h>
| ||||
|
| |||
TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn. |
#include <CGAL/ch_graham_andrew.h>
| ||||
|
| |||
TRAITS: operates on Traits::Point_2 using Traits::Leftturn and Traits::Less_xy. |
#include <CGAL/ch_eddy.h>
| ||||
|
| |||
TRAITS: uses the types Traits::Point_2, Traits::Less_dist_to_line, Traits::Right_of_line, and Traits::Less_xy. |
#include <CGAL/ch_bykat.h>
| ||||
|
| |||
TRAITS: uses the types Traits::Point_2, Traits::Less_dist_to_line, Traits::Right_of_line, and Traits::Less_xy. |
#include <CGAL/ch_jarvis.h>
| ||||
|
| |||
TRAITS: uses types Traits::Point_2, Traits::Less_rotate_ccw, and Traits::Less_xy. |
#include <CGAL/basic.h> #include <list.h> #include <CGAL/Cartesian.h> #include <CGAL/Point_2.h> #include <CGAL/convex_hull_2.h> #include <CGAL/Polygon_2.h> typedef CGAL_Cartesian<int> RepCls; typedef CGAL_Point_2<RepCls> Point_2; typedef CGAL_Polygon_2<RepCls, list<Point_2> > Polygon_2; int main() { Polygon_2 CH; istream_iterator< Point_2, ptrdiff_t > in_start( cin ); istream_iterator< Point_2, ptrdiff_t > in_end; CGAL_convex_hull_points_2( in_start, in_end, inserter(CH, CH.vertices_begin()) ); CGAL_Window_stream W( 512, 512, 50, 50); W.init( -256.0, 255.0, -256.0); W << CH; Point_2 p; W >> p; // wait for mouse click in window return 0; }
#include <CGAL/convex_hull_2.h>
| ||||
|
| |||
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 . TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn. | ||||
| ||||
|
| |||
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. leftmost and rightmost point are equal) the extreme
point is not reported. Precondition: The source range [first,beyond) does not contain result. TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn. |
The different treatment of the case that all points are equal ensures that concatenation of lower and upper hull points gives the sequence of extreme points.
CGAL provides some functions to compute certain subsequences of the sequence of extreme points on the convex hull.
| ||||
|
| |||
generates the counterclockwise ordered subsequence of extreme
points between start_p and stop_p of the points in
the range [first,beyond), starting at position result
with point start_p. The last point generated is the point
preceding stop_p in the counterclockwise order of extreme
points. Precondition: start_p and stop_p are extreme points with respect to the points in the range [first,beyond) and stop_p is an element of range [first,beyond). TRAITS: uses Traits::Less_rotate_ccw. | ||||
| ||||
|
| |||
computes the sorted sequence of extreme points which are not left
of , where is the value of
first and is the value of beyond
. It reports this sequence counterclockwise in a
range starting at result, starting with ;
point is omitted.
Precondition: The range [first, beyond) contains at least two different points. The points in [first,beyond) are ``sorted'' with respect to , i.e. the sequence of points in [first, beyond) define a counterclockwise polygon, for which the Graham-Sklansky-procedure works. TRAITS: uses Traits::Leftturn operating on the point type Traits::Point_2. |
template <class InputIterator, class OutputIterator, class Traits> OutputIterator CGAL_ch_graham_anderson( InputIterator first, InputIterator beyond, OutputIterator result, const Traits& ch_traits) { typedef typename Traits::Less_xy Less_xy; typedef typename Traits::Point_2 Point_2; typedef typename Traits::Less_rotate_ccw Less_rotate_ccw; if (first == beyond) return result; vector< Point_2 > V; copy( first, beyond, back_inserter(V) ); vector< Point_2 >::iterator it = min_element(V.begin(), V.end(), Less_xy()); sort( V.begin(), V.end(), Less_rotate_ccw(*it) ); if ( *(V.begin()) == *(V.rbegin()) ) { *result = *(V.begin()); ++result; return result; } return CGAL_ch_graham_andrew_scan( V.begin(), V.end(), res, ch_traits); }Anderson's variant of the Graham scan is usually inferior to Andrew's variant because of its higher arithmetic demand.
#include <CGAL/ch_selected_extreme_points_2.h>
| ||||
|
| |||
traverses the range [first,beyond). After execution,
the value of n is an iterator in the range such that
*n *it for all
iterators it in the range. Similarly, for s, w
, and e the inequalities *s
*it, *w
*it, and *e
*it hold respectively for
all iterators it in the range. TRAITS: uses the types Traits::Less_xy, and Traits::Less_yx. |
Analogously, we have
| ||||
|
| |||
| ||||
|
| |||
| ||||
|
| |||
| ||||
|
| |||
| ||||
|
| |||
| ||||
|
|
| ||||
|
| |||
returns true, iff the point elements in [first,
beyond) form a counterclockwise oriented strongly convex
polygon. TRAITS: uses Traits::Leftturn and Traits::Less_xy. | ||||
| ||||
|
| |||
returns true, iff the point elements in [first,
beyond) form a clockwise oriented strongly convex
polygon. TRAITS: uses Traits::rightturn() and Traits::Less_xy. |
The convex hull algorithms in Section are
parameterized with a traits class Traits. Besides the traits class
CGAL_convex_hull_traits_2<R> used in the default versions of
the functions, CGAL provides a traits class
CGAL_convex_hull_constructive_traits_2<R> which also uses
CGAL primitives and reuses intermediate results to
speed up computation.
Requirements on a traits class for convex hull algorithms are listed in
Section
.
The convex hull algorithms in Section are
parameterized with a traits class Traits which defines the
primitives (objects and predicates) that the convex hull algorithms use.
The following catalog lists the primitives involved in the
convex hull and extreme point functions. The primitives that are actually
required for a function are listed with the specification of the function
in Section
.
Available convex hull traits classes implementations provided by CGAL are described in Section .
#include <CGAL/convex_hull_3.h>
#include <CGAL/Cartesian.h> #include <CGAL/Point_3.h> #include <CGAL/point_generators_3.h> #include <CGAL/copy_n.h> #include <CGAL/Halfedge_data_structure_polyhedron_default_3.h> #include <CGAL/Polyhedron_default_traits_3.h> #include <CGAL/Polyhedron_3.h> #include <CGAL/IO/Polyhedron_geomview_ostream.h> #include <CGAL/convex_hull_3.h> #include <vector> /* representation class */ typedef CGAL_Cartesian<double> RepCls; /* define polyhedron type */ typedef CGAL_Halfedge_data_structure_polyhedron_default_3<RepCls> HDS; typedef CGAL_Polyhedron_default_traits_3<RepCls> PolyTraits; typedef CGAL_Polyhedron_3< PolyTraits, HDS> Polyhedron; /* define point creator */ typedef CGAL_Point_3<RepCls> Point; typedef CGAL_Creator_uniform_3<double,Point> PointCreator; int main() { /* generate 250 points randomly on a sphere of radius 100.0 */ CGAL_Random_points_in_sphere_3< Point, PointCreator> gen(100.0); /* and copy them to a vector */ vector<Point> V; CGAL_copy_n( gen, 250, back_inserter(V) ); /* define polyhedron to hold convex hull */ Polyhedron P; /* compute convex hull */ CGAL_convex_hull_3( V.begin(), V.end(), P); /* visualize it using geomview - wait for mouse click */ CGAL_Geomview_stream gvs; gvs << P; Point click; gvs >> click; }