CGAL 4.7 - 2D Convex Hulls and Extreme Points: Hull Subsequence Functions

\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)

CGAL 4.7 - 2D Convex Hulls and Extreme Points

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
Functions
Hull Subsequence Functions
2D Convex Hulls and Extreme Points Reference

##

## Functions

template<class BidirectionalIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_graham_andrew_scan (BidirectionalIterator first, BidirectionalIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line defined by the first and last points in this sequence. More...
template<class ForwardIterator , class OutputIterator , class Traits >
OutputIterator | CGAL::ch_jarvis_march (ForwardIterator first, ForwardIterator beyond, const Traits::Point_2 &start_p, const Traits::Point_2 &stop_p, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points from a given set of input points that line between two input points. More...
template<class InputIterator , class OutputIterator >
OutputIterator | CGAL::lower_hull_points_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points on the lower hull of a given set of input points. More...
template<class InputIterator , class OutputIterator >
OutputIterator | CGAL::upper_hull_points_2 (InputIterator first, InputIterator beyond, OutputIterator result, const Traits &ch_traits=Default_traits)
| generates the counterclockwise sequence of extreme points on the upper hull of a given set of input points. More...

## Function Documentation

template<class BidirectionalIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_graham_andrew_scan | ( | BidirectionalIterator | first,
|  | BidirectionalIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line defined by the first and last points in this sequence.

More precisely, it generates the counterclockwise sequence of extreme points from a given sequence of input points that are not left of the line \( pq\) defined by the first ( \(p\)) and last ( \(q\)) points in this sequence ( \( 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 [11] works.

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

Requirements

1. `BidirectionalIterator::value_type` and `OutputIterator::value_type` are equivalent to `Traits::Point_2`.
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`.

See Also
  `CGAL::ch_graham_andrew()`
  `CGAL::lower_hull_points_2()`
  `CGAL::upper_hull_points_2()`

Implementation

This algorithm requires \( O(n)\) time in the worst case for \( n\) input points.

Example

In the example Convex_hull_2/ch_graham_anderson.cpp, `ch_graham_andrew_scan()` is used to realize Anderson's variant [2] of the Graham Scan [7]. 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.

`#include <CGAL/ch_graham_andrew.h>`

Examples:
  Convex_hull_2/ch_graham_anderson.cpp.

template<class ForwardIterator , class OutputIterator , class Traits >

OutputIterator CGAL::ch_jarvis_march | ( | ForwardIterator | first,
|  | ForwardIterator | beyond,
|  | const Traits::Point_2 & | start_p,
|  | const Traits::Point_2 & | stop_p,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

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

More precisely, it 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.

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 [8]. This algorithm requires \( O(n h)\) time in the worst case for \( n\) input points with \( h\) 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`).

`#include <CGAL/ch_jarvis.h>`

template<class InputIterator , class OutputIterator >

OutputIterator CGAL::lower_hull_points_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points on the lower hull of a given set of input points.

More precisely, it 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`.

The default traits class `Default_traits` is the kernel in which the value type of `InputIterator` is defined.

The different treatment by `upper_hull_points_2()` of the case that all points are equal ensures that concatenation of lower and upper hull points gives the sequence of extreme points.

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` contains 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_xy_2`,
   - `Traits::Less_yx_2`,
   - `Traits::Left_turn_2`.

See Also
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_graham_andrew_scan()`
  `CGAL::upper_hull_points_2()`

Implementation

This function uses Andrew's variant of Graham's scan algorithm [3], [9]. The algorithm has worst-case running time of \( O(n \log n)\) for \( n\) input points.

`#include <CGAL/convex_hull_2.h>`

template<class InputIterator , class OutputIterator >

OutputIterator CGAL::upper_hull_points_2 | ( | InputIterator | first,
|  | InputIterator | beyond,
|  | OutputIterator | result,
|  | const Traits & | ch_traits = `Default_traits`
| ) |  |

generates the counterclockwise sequence of extreme points on the upper hull of a given set of input points.

More precisely, it 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., the leftmost and rightmost point are equal), the extreme point is not reported.

Precondition
  The source range [`first`,`beyond`) does not contain `result`.

The default traits class `Default_traits` is the kernel in which the value type of `InputIterator` is defined.

The different treatment by `lower_hull_points_2()` of the case that all points are equal ensures that concatenation of lower and upper hull points gives the sequence of extreme points.

Requirements

1. The value type of `InputIterator` and `OutputIterator` is equivalent to `Traits::Point_2`.
2. `Traits` contains 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_xy_2`,
   - `Traits::Less_yx_2`,
   - `Traits::Left_turn_2`.

See Also
  `CGAL::ch_graham_andrew()`
  `CGAL::ch_graham_andrew_scan()`
  `CGAL::lower_hull_points_2()`

Implementation

This function uses Andrew's variant of Graham's scan algorithm [3], [9]. The algorithm has worst-case running time of \( O(n \log n)\) for \( n\) input points.

`#include <CGAL/convex_hull_2.h>`