Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## CGAL::ch_akl_toussaint

### Definition

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

#include <CGAL/ch_akl_toussaint.h>

template <class ForwardIterator, class OutputIterator, class Traits>
OutputIterator |
ch_akl_toussaint ( | ForwardIterator first, ForwardIterator 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 ForwardIterator::value_type is defined.

### Requirements

1. ForwardIterator::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:
   - Traits::Point_2,
   - Traits::Less_xy_2,
   - Traits::Less_yx_2,
   - Traits::Left_turn_2,
   - Traits::Equal_2.

### See Also

CGAL::ch_bykat
CGAL::ch_eddy
CGAL::ch_graham_andrew
CGAL::ch_jarvis
CGAL::ch_melkman
CGAL::convex_hull_2

### Implementation

This function uses the algorithm of Akl and Toussaint [AT78] that requires O(n logn) time for n input points.

Next: ch_bykat

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .