CGAL 4.7 - 2D Convex Hulls and Extreme Points: ConvexHullTraits_2 Concept Reference

\( \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
List of all members
ConvexHullTraits_2 Concept Reference
Concepts

## Definition

All convex hull and extreme point algorithms provided in CGAL are parameterized with a traits class `Traits`, which defines the primitives (objects and predicates) that the convex hull algorithms use. `ConvexHullTraits_2` defines the complete set of primitives required in these functions. The specific subset of these primitives required by each function is specified with each function.

Has Models:

  `CGAL::Convex_hull_constructive_traits_2<R>`

  `CGAL::Convex_hull_traits_2<R>`

  `CGAL::Projection_traits_xy_3<K>`

  `CGAL::Projection_traits_yz_3 <K>`

  `CGAL::Projection_traits_xz_3<K>`

See Also
  `IsStronglyConvexTraits_3`

## Types

typedef unspecified_type | Point_2
| The point type on which the convex hull functions operate.
typedef unspecified_type | Equal_2
| Binary predicate object type comparing `Point_2`s. More...
typedef unspecified_type | Less_xy_2
| Binary predicate object type comparing `Point_2`s lexicographically. More...
typedef unspecified_type | Less_yx_2
| Same as `Less_xy_2` with the roles of \( x\) and \( y\) interchanged.
typedef unspecified_type | Left_turn_2
| Predicate object type that must provide `bool operator()(Point_2 p,Point_2 q,Point_2 r)`, which returns `true` iff `r` lies to the left of the oriented line through `p` and `q`.
typedef unspecified_type | Less_signed_distance_to_line_2

Predicate object type that must provide `bool operator()(Point_2 p, Point_2 q, Point_2 r,Point_2 s)`, which returns `true` iff the signed distance from \( r\) to the line \( l_{pq}\) through \( p\) and \( q\) is smaller than the distance from \( s\) to \( l_{pq}\). More...

typedef unspecified_type | Less_rotate_ccw_2

Predicate object type that must provide `bool operator()(Point_2 e, Point_2 p,Point_2 q)`, where `true` is returned iff a tangent at \( e\) to the point set \( \{e,p,q\}\) hits \( p\) before \( q\) when rotated counterclockwise around \( e\). More...

## Creation

Only a copy constructor is required.
| ConvexHullTraits_2 (ConvexHullTraits_2 &t)

## Operations

The following member functions to create instances of the above predicate object types must exist.
Equal_2 | equal_2_object ()
Less_xy_2 | less_xy_2_object ()
Less_yx_2 | less_yx_2_object ()
Less_signed_distance_to_line_2 | less_signed_distance_to_line_2_object ()
Less_rotate_ccw_2 | less_rotate_ccw_2_object ()
Left_turn_2 | left_turn_2_object ()

## Member Typedef Documentation

typedef unspecified_type ConvexHullTraits_2::Equal_2

Binary predicate object type comparing `Point_2`s.

Must provide `bool operator()(Point_2 p, Point_2 q)` where `true` is returned iff \( p ==_{xy} q\), false otherwise.

typedef unspecified_type ConvexHullTraits_2::Less_rotate_ccw_2

Predicate object type that must provide `bool operator()(Point_2 e, Point_2 p,Point_2 q)`, where `true` is returned iff a tangent at \( e\) to the point set \( \{e,p,q\}\) hits \( p\) before \( q\) when rotated counterclockwise around \( e\).

Ties are broken such that the point with larger distance to \( e\) is smaller!

typedef unspecified_type ConvexHullTraits_2::Less_signed_distance_to_line_2

Predicate object type that must provide `bool operator()(Point_2 p, Point_2 q, Point_2 r,Point_2 s)`, which returns `true` iff the signed distance from \( r\) to the line \( l_{pq}\) through \( p\) and \( q\) is smaller than the distance from \( s\) to \( l_{pq}\).

It is used to compute the point right of a line with maximum unsigned distance to the line. The predicate must provide a total order compatible with convexity, i.e., for any line segment \( s\) one of the endpoints of \( s\) is the smallest point among the points on \( s\), with respect to the order given by `Less_signed_distance_to_line_2`.

typedef unspecified_type ConvexHullTraits_2::Less_xy_2

Binary predicate object type comparing `Point_2`s lexicographically.

Must provide `bool operator()(Point_2 p, Point_2 q)` where `true` is returned iff \( p <_{xy} q\). We have \( p<_{xy}q\), iff \( p_x < q_x\) or \( p_x = q_x\) and \( p_y < q_y\), where \( p_x\) and \( p_y\) denote \( x\) and \( y\) coordinate of point \( p\), respectively.