The function ch_graham_andrew_scan generates the counterclockwise sequence of extreme points from a given set of input points that are not left of the line defined by the first and last points in this sequence.
#include <CGAL/ch_graham_andrew.h>
| ||||
|
| |||
generates the counterclockwise sequence of extreme points that are
not left of , where is the value of first and is
the value of beyond . The resulting sequence is placed
starting at result with ; point is omitted. The
past-the-end iterator for the sequence is returned.
|
The default traits class Default_traits is the kernel in which the type BidirectionalIterator::value_type is defined.
CGAL::ch_graham_andrew
CGAL::lower_hull_points_2
CGAL::upper_hull_points_2
The function uses Andrew's variant of the Graham scan algorithm [And79] . This algorithm requires log time in the worst case for input points.
In the following example ch_graham_andrew_scan() is used to realize Anderson's variant [And78] of the Graham Scan [Gra72]. The points are sorted counterclockwise around the leftmost point using the Less_rotate_ccw_2 predicate, as defined in the concept ConvexHullTraits_2. According to the definition of Less_rotate_ccw_2, the leftmost point is the last point in the sorted sequence and its predecessor on the convex hull is the first point in the sorted sequence. It is not hard to see that the preconditions of ch_graham_andrew_scan() are satisfied. Anderson's variant of the Graham scan is usually inferior to Andrew's variant because of its higher arithmetic demand.
template <class InputIterator, class OutputIterator, class Traits> OutputIterator ch_graham_anderson( InputIterator first, InputIterator beyond, OutputIterator result, const Traits& ch_traits) { typedef typename Traits::Less_xy_2 Less_xy_2; typedef typename Traits::Point_2 Point_2; typedef typename Traits::Less_rotate_ccw_2 Less_rotate_ccw_2; if (first == beyond) return result; std::vector< Point_2 > V; copy( first, beyond, back_inserter(V) ); typename std::vector< Point_2 >::iterator it = std::min_element(V.begin(), V.end(), Less_xy_2()); std::sort( V.begin(), V.end(), CGAL::bind_1(Less_rotate_ccw_2(), *it) ); if ( *(V.begin()) == *(V.rbegin()) ) { *result = *(V.begin()); ++result; return result; } return ch_graham_andrew_scan( V.begin(), V.end(), result, ch_traits); }