\( \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.12 - 2D Convex Hulls and Extreme Points
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

◆ ch_graham_andrew_scan()

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 
)

#include <CGAL/ch_graham_andrew.h>

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.

Examples:
Convex_hull_2/ch_graham_anderson.cpp.

◆ ch_jarvis_march()

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 
)

#include <CGAL/ch_jarvis.h>

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).

◆ lower_hull_points_2()

template<class InputIterator , class OutputIterator >
OutputIterator CGAL::lower_hull_points_2 ( InputIterator  first,
InputIterator  beyond,
OutputIterator  result,
const Traits &  ch_traits = Default_traits 
)

#include <CGAL/convex_hull_2.h>

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.

◆ upper_hull_points_2()

template<class InputIterator , class OutputIterator >
OutputIterator CGAL::upper_hull_points_2 ( InputIterator  first,
InputIterator  beyond,
OutputIterator  result,
const Traits &  ch_traits = Default_traits 
)

#include <CGAL/convex_hull_2.h>

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.