2D Convex Hulls and Extreme Points

Introduction

A subset $$S ² is convex if for any two points $$p and $$q in the set the line segment with endpoints $$p and $$q is contained in $$S. The convex hull of a set $$S is the smallest convex set containing $$S. The convex hull of a set of points $$P is a convex polygon with vertices in $$P. A point in $$P is an extreme point (with respect to $$P) if it is a vertex of the convex hull of $$P. A set of points is said to be strongly convex if it consists of only extreme points.

This chapter describes the functions provided in CGAL for producing convex hulls in two dimensions as well as functions for checking if sets of points are strongly convex are not. There are also a number of functions described for computing particular extreme points and subsequences of hull points, such as the lower and upper hull of a set of points.

Convex Hull

Each of the convex hull functions presents the same interface to the user. That is, the user provides a pair of iterators, first and beyond, an output iterator result, and a traits class traits. The points in the range [first, beyond) define the input points whose convex hull is to be computed. The counterclockwise sequence of extreme points is written to the sequence starting at position result, and the past-the-end iterator for the resulting set of points is returned. The traits classes for the functions specify the types of the input points and the geometric primitives that are required by the algorithms. All functions provide an interface in which this class need not be specified and defaults to types and operations defined in the kernel in which the input point type is defined.

Given a sequence of $$n input points with $$h extreme points, the function convex_hull_2 uses either the output-sensitive $$O(n h) algorithm of Bykat [Byk78] (a non-recursive version of the quickhull [BDH96] algorithm) or the algorithm of Akl and Toussaint, which requires $$O(n log$$n) time in the worst case. The algorithm chosen depends on the kind of iterator used to specify the input points. These two algorithms are also available via the functions ch_bykat and ch_akl_toussaint, respectively. Also available are the $$O(n log$$n) Graham-Andrew scan algorithm [And79, Meh84] (ch_graham_andrew), the $$O(n h) Jarvis march algorithm [Jar73] (ch_jarvis), and Eddy's $$O(n h) algorithm [Edd77] (ch_eddy), which corresponds to the two-dimensional version of the quickhull algorithm. The linear-time algorithm of Melkman for producing the convex hull of simple polygonal chains (or polygons) is available through the function ch_melkman.

Example using Bykat's algorithm

In the following example a convex hull is constructed from point data read from standard input using Bykat's algorithm. The resulting convex polygon is stored in a CGAL::Polygon_2 and then it is shown in a CGAL window. The default traits class is used here. The same results could be achieved by substituting the function CGAL::ch_bykat for CGAL::convex_hull_2, since the latter calls the former when the input points are specified using input interators.

//
// file: demo/Convex_hull_2/convex_hull_2_demo.C
//
#include <CGAL/Cartesian.h>
#include <CGAL/convex_hull_2.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/IO/Window_stream.h>
#include <list>

typedef CGAL::Cartesian<int>                     K;
typedef K::Point_2                               Point_2;
typedef CGAL::Polygon_2<K, std::list<Point_2> >  Polygon_2;

int main()
{
  Polygon_2                         CH;
  std::istream_iterator< Point_2 >  in_start( std::cin );
  std::istream_iterator< Point_2 >  in_end;

  CGAL::convex_hull_2( in_start, in_end,
                       std::inserter(CH, CH.vertices_begin()) );
  CGAL::Window_stream  W;
  W.init( -256.0, 255.0, -256.0);
  W.display();
  W << CH;

  W.read_mouse();          // wait for mouse click in window
  return 0;
}

Extreme Points and Hull Subsequences

There are also functions available for computing certain subsequences of the sequence of extreme points on the convex hull. The function ch_jarvis_march generates the counterclockwise ordered subsequence of extreme points between a given pair of points and ch_graham_andrew_scan computes the sorted sequence of extreme points that are not left of the line defined by the first and last input points.

Finally, a set of functions (ch_nswe_point, ch_ns_point, ch_we_point, ch_n_point, ch_s_point, ch_w_point, ch_e_point) is provided for computing extreme points of a 2D point set in the coordinate directions.

Traits Classes

Each of the functions used to compute convex hulls or extreme points is paramterized by a traits class, which specifies the types and geometric primitives to be used in the computation. There are several implementations of 2D traits classes provided in the library. The class Convex_hull_traits_2<R> corresponds to the default traits class that provides the types and predicates presented in the 2-dimensional CGAL kernel in which the input points lie. The class Convex_hull_constructive_traits<R> is a second traits class based on CGAL primitives but differs from Convex_hull_traits_2 in that some of its primitives reuse intermediate results to speed up computation. There are also two traits classes defined for the two geometry kernels provided in LEDA [MN99b] (Convex_hull_leda_traits_2 and Convex_hull_rat_leda_traits_2), which provide an easy means of comparison with these kernels. In addition, there are three projective traits classes (Convex_hull_projective_xy_traits_2, Convex_hull_projective_xz_traits_2, and Convex_hull_projective_yz_traits_2), which may be used to compute the convex hull of a set of three-dimensional points projected into each of the three coordinate planes.

Convexity Checking

The functions is_ccw_strongly_convex_2 and is_cw_strongly_convex_2 check whether a given sequence of 2D points forms a (counter)clockwise strongly convex polygon.. These are used in postcondition testing of the two-dimensional convex hull functions.