ch_graham_andrew

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

CGAL::ch_graham_andrew_scan

Definition

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>

template <class BidirectionalIterator, class OutputIterator, class Traits>

OutputIterator

ch_graham_andrew_scan ( BidirectionalIterator first,
BidirectionalIterator beyond,
OutputIterator result,
Traits ch_traits = Default_traits)

generates the counterclockwise sequence of extreme points that are not left of pq, where p is the value of first and q is the value of beyond -1. The resulting sequence is placed starting at result with p; point q is omitted. The past-the-end iterator for the sequence is returned.

Precondition:

The range [first,beyond) contains at least two different points. The points in [first,beyond) are ``sorted'' with respect to pq, i.e., the sequence of points in [first,beyond) define a counterclockwise polygon, for which the Graham-Sklansky-procedure [Skl72] works.

The default traits class Default_traits is the kernel in which the type BidirectionalIterator::value_type is defined.

Requirements

BidirectionalIterator::value_type and OutputIterator::value_type are equivalent to Traits::Point_2.
Traits defines the following two types from the concept ConvexHullTraits_2 and their corresponding member functions that return instances of these types:
- Traits::Point_2,
- Traits::Left_turn_2.

Implementation

The function uses Andrew's variant of the Graham scan algorithm [And79] . This algorithm requires O(n log n) time in the worst case for n input points.

Example

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);
}

Next: ch_jarvis