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

## CGAL::ch_jarvis_march

### Definition

The function ch_jarvis_march generates the counterclockwise sequence of extreme points from a given set of input points that line between two input points.

#include <CGAL/ch_jarvis.h>

template <class ForwardIterator, class OutputIterator, class Traits>
OutputIterator |
ch_jarvis_march ( | ForwardIterator first, ForwardIterator beyond, Traits::Point_2 start_p, Traits::Point_2 stop_p, OutputIterator result, Traits ch_traits = Default_traits)
|  | generates the counterclockwise 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).

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::Equal_2,
   - Traits::Less_rotate_ccw_2.

### See Also

CGAL::ch_jarvis
CGAL::lower_hull_points_2
CGAL::upper_hull_points_2

### Implementation

The function uses the Jarvis march (gift-wrapping) algorithm [Jar73]. This algorithm requires O(n h) time in the worst case for n input points with h extreme points.

Next: ch_melkman

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

The CGAL Project . Tue, December 21, 2004 .