Convex Hulls and Extreme Points

Planar Convex Hull and Extreme Points

Definition

A subset $$S of the plane is convex if with 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.

CGAL provides functions computing the counterclockwise sequence of extreme points for a set of points, i.e. the counterclockwise sequence of points on the convex hull of the set of points. Furthermore, functions computing special extreme points are provided. Finally, there are functions that check whether a given sequence of points forms a (counter)clockwise convex polygon.

The last parameter Traits in the convex hull and extreme point functions is a traits class that defines the primitives that are used in the algorithms. For example Traits::Point_2 is a mapping on a point class.

CGAL provides implementations of convex hull traits classes as described in . A default implementation convex_hull_traits_2<R> is provided for the two-dimensional CGAL kernel. This traits class is used in default versions of the functions that do not have a traits class parameter. Such default versions exists for all the functions specified below. Own convex hull traits classes can be designed according to the requirements for such traits classes listed in .

Assertions

Convex Hull

#include <CGAL/convex_hull_2.h>

template <class InputIterator, class OutputIterator>
OutputIterator	convex_hull_points_2 ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		generates the counterclockwise sequence of extreme points 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. It is not specified at which point the cyclic sequence of extreme points is cut into a linear sequence. Precondition: The source range [first,beyond) does not contain result. TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn.

Besides the default algorithm for computing convex hulls, implementations of some classical convex hull algorithms are available, with the same semantics as the default algorithm.

#include <CGAL/ch_akl_toussaint.h>

template <class ForwardIterator, class OutputIterator, class Traits>
OutputIterator	ch_akl_toussaint ( ForwardIterator first, ForwardIterator beyond, OutputIterator result, Traits ch_traits)
		TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn.

#include <CGAL/ch_graham_andrew.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator	ch_graham_andrew ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		TRAITS: operates on Traits::Point_2 using Traits::Leftturn and Traits::Less_xy.

#include <CGAL/ch_eddy.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator	ch_eddy ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		TRAITS: uses the types Traits::Point_2, Traits::Less_dist_to_line, Traits::Right_of_line, and Traits::Less_xy.

#include <CGAL/ch_bykat.h>

template <class InputIterator, class OutputIterator, class Traits>
OutputIterator	ch_bykat ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		TRAITS: uses the types Traits::Point_2, Traits::Less_dist_to_line, Traits::Right_of_line, and Traits::Less_xy.

#include <CGAL/ch_jarvis.h>

template <class ForwardIterator, class OutputIterator, class Traits>
OutputIterator	ch_jarvis ( ForwardIterator first, ForwardIterator beyond, OutputIterator result, Traits ch_traits)
		TRAITS: uses types Traits::Point_2, Traits::Less_rotate_ccw, and Traits::Less_xy.

Implementation

Example

#include <CGAL/basic.h>
#include <list>
#include <CGAL/Cartesian.h>
#include <CGAL/Point_2.h>
#include <CGAL/convex_hull_2.h>
#include <CGAL/Polygon_2.h>

using namespace std;

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

int
main()
{
  Polygon_2                                  CH;
  istream_iterator< Point_2, ptrdiff_t >     in_start( cin );
  istream_iterator< Point_2, ptrdiff_t >     in_end;

  CGAL::convex_hull_points_2( in_start, in_end,
                              inserter(CH, CH.vertices_begin()) );
  CGAL::Window_stream  W( 512, 512, 50, 50);
  W.init( -256.0, 255.0, -256.0);
  W << CH;

  Point_2  p;
  W >> p;          // wait for mouse click in window
  return 0;
}

Lower Hull and Upper Hull

#include <CGAL/convex_hull_2.h>

template <class InputIterator, class OutputIterator>
OutputIterator	lower_hull_points_2 ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		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. TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn.
template <class InputIterator, class OutputIterator>
OutputIterator	upper_hull_points_2 ( InputIterator first, InputIterator beyond, OutputIterator result, Traits ch_traits)
		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. leftmost and rightmost point are equal) the extreme point is not reported. Precondition: The source range [first,beyond) does not contain result. TRAITS: uses Traits::Point_2, Traits::Less_xy, Traits::Less_yx, Traits::Right_of_line, and Traits::Leftturn.

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

Convex Hull of Simple Polygons and Polylines

#include <CGAL/ch_melkman.C>

template <class InputIterator, class OutputIterator>
OutputIterator	ch_melkman ( InputIterator first, InputIterator last, OutputIterator result)
		generates the counterclockwise sequence of extreme points of the points in the range [first, beyond), provided that the sequence of points must correspond to a simple polyline. The resulting sequence is placed starting at position result, and the past-the-end iterator for the resulting sequence is returned. Precondition: The source range [first,beyond) corresponds to a simple polyline. [first,beyond) does not contain result. TRAITS: uses Traits::Point_2, Traits::Less_xy and Traits::Leftturn.

Convex Hull Utilities

CGAL provides some functions to compute certain subsequences of the sequence of extreme points on the convex hull.

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)
		generates the counterclockwise ordered 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). TRAITS: uses Traits::Less_rotate_ccw.
template <class BidirectionalIterator, class OutputIterator, class Traits>
OutputIterator	ch_graham_andrew_scan ( BidirectionalIterator first, BidirectionalIterator beyond, OutputIterator result, Traits ch_traits)
		computes the sorted sequence of extreme points which are not left of $$pq, where $$p is the value of first and $$q is the value of beyond $$-1. It reports this sequence counterclockwise in a range starting at result, starting with $$p; point $$q is omitted. 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 works. TRAITS: uses Traits::Leftturn operating on the point type Traits::Point_2.

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 predicate, see . According to the definition of Less_rotate_ccw, 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 precondition of ch_graham_andrew_scan() are satisfied.

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          Less_xy;
  typedef typename Traits::Point_2          Point_2;
  typedef typename Traits::Less_rotate_ccw  Less_rotate_ccw;

  if (first == beyond) return result;
  vector< Point_2 >  V;
  copy( first, beyond, back_inserter(V) );
  vector< Point_2 >::iterator it = min_element(V.begin(), V.end(), Less_xy());
  sort( V.begin(), V.end(), Less_rotate_ccw(*it) );
  if ( *(V.begin()) == *(V.rbegin()) )
  {
      *result = *(V.begin());  ++result;
      return result;
  }
  return ch_graham_andrew_scan( V.begin(), V.end(), res, ch_traits);
}

Extreme Points in Coordinate Directions

#include <CGAL/ch_selected_extreme_points_2.h>

template <class ForwardIterator>
void	ch_nswe_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& n, ForwardIterator& s, ForwardIterator& w, ForwardIterator& e, Traits ch_traits)
		traverses the range [first,beyond). After execution, the value of n is an iterator in the range such that *n $$ yx *it for all iterators it in the range. Similarly, for s, w, and e the inequalities *s $$ yx *it, *w $$ xy *it, and *e $$ xy *it hold respectively for all iterators it in the range. TRAITS: uses the types Traits::Less_xy, and Traits::Less_yx.

Analogously, we have

template <class ForwardIterator>
void	ch_we_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& w, ForwardIterator& e, Traits ch_traits)
template <class ForwardIterator>
void	ch_ns_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& n, ForwardIterator& s, Traits ch_traits)
template <class ForwardIterator>
void	ch_n_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& n, Traits ch_traits)
template <class ForwardIterator>
void	ch_s_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& s, Traits ch_traits)
template <class ForwardIterator>
void	ch_w_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& w, Traits ch_traits)
template <class ForwardIterator>
void	ch_e_point ( ForwardIterator first, ForwardIterator beyond, ForwardIterator& e, Traits ch_traits)

Convexity Checking

template <class ForwardIterator, class Traits>
bool	is_ccw_strongly_convex_2 ( ForwardIterator first, ForwardIterator beyond, Traits ch_traits)
		returns true, iff the point elements in [first,beyond) form a counterclockwise oriented strongly convex polygon. TRAITS: uses Traits::Leftturn and Traits::Less_xy.
template <class ForwardIterator, class Traits>
bool	is_cw_strongly_convex_2 ( ForwardIterator first, ForwardIterator beyond, Traits ch_traits)
		returns true, iff the point elements in [first,beyond) form a clockwise oriented strongly convex polygon. TRAITS: uses Traits::rightturn() and Traits::Less_xy.

Convex Hull Traits Class Implementations

The convex hull algorithms in Section  are parameterized with a traits class Traits. Besides the traits class convex_hull_traits_2<R> used in the default versions of the functions, CGAL provides a traits class convex_hull_constructive_traits_2<R> which also uses CGAL primitives and reuses intermediate results to speed up computation. Requirements on a traits class for convex hull algorithms are listed in Section .

• Class declaration of convex_hull_traits_2<R>.

• Class declaration of convex_hull_constructive_traits_2<R>.

Convex Hull Traits Classes for LEDA geometry

• Class declaration of convex_hull_rat_leda_traits_2.

• Class declaration of convex_hull_leda_traits_2.

Convex Hulls Traits Class Requirements

The convex hull algorithms in Section  are parameterized with a traits class Traits which defines the primitives (objects and predicates) that the convex hull algorithms use. The following catalog lists the primitives involved in the convex hull and extreme point functions. The primitives that are actually required for a function are listed with the specification of the function in Section .

Available convex hull traits classes implementations provided by CGAL are described in Section .

• Class declaration of Traits.

3D Convex Hull

#include <CGAL/convex_hull_3.h>

template <class InputIterator, class Polyhedron>
void	convex_hull_3 ( InputIterator first, InputIterator beyond, Polyhedron& P)
		Computes the convex hull polyhedron of the points in the range [first,beyond) and assigns it to P. Precondition: Value type of the iterator and the point type of the Polyhedron are Point_3<R> for some representation class R.

Implementation

Example

The following example uses CGAL's 3D random point generator Random_points_in_sphere_3<>, which generates random points on a sphere, and CGAL's STL extension function copy_n, which copies $$n elements.

#include <CGAL/Cartesian.h>
#include <CGAL/Point_3.h>
#include <CGAL/point_generators_3.h>
#include <CGAL/copy_n.h>
#include <CGAL/Halfedge_data_structure_polyhedron_default_3.h>
#include <CGAL/Polyhedron_default_traits_3.h>
#include <CGAL/Polyhedron_3.h>
#include <CGAL/IO/Polyhedron_geomview_ostream.h>
#include <CGAL/convex_hull_3.h>
#include <vector>

/* representation class */
typedef CGAL::Cartesian<double>                                     RepCls;

/* define polyhedron type */
typedef CGAL::Halfedge_data_structure_polyhedron_default_3<RepCls>  HDS;
typedef CGAL::Polyhedron_default_traits_3<RepCls>                   PolyTraits;
typedef CGAL::Polyhedron_3< PolyTraits, HDS>                        Polyhedron;

/* define point creator */
typedef CGAL::Point_3<RepCls>                                       Point;
typedef CGAL::Creator_uniform_3<double,Point>                       PointCreator;

using namespace std;

int 
main()
{
  /* generate 250 points randomly on a sphere of radius 100.0 */
  Random_points_in_sphere_3< Point, PointCreator> gen(100.0);

  /* and copy them to a vector */
  vector<Point> V;
  CGAL::copy_n( gen, 250, back_inserter(V) );
  
  /* define polyhedron to hold convex hull */
  Polyhedron P;

  /* compute convex hull */
  CGAL::convex_hull_3( V.begin(), V.end(), P);

  /* visualize it using geomview - wait for mouse click */
  CGAL::Geomview_stream gvs;
  gvs << P;
  Point click;
  gvs >> click;
}

Chull Traits Classes

• Class declaration of chull_traits_2<R>.

• Class declaration of chull_traits_3<R>.

Conversion to Polyhedron

• Class declaration of Build_polyhedron_from_GRAPH<HDS>.

• Class declaration of Build_polyhedron_from_chull<HDS, ChullType>.