CGAL 6.1.1 - 2D Convex Hulls and Extreme Points

Loading...
Searching...
No Matches
List of all members
ConvexHullTraits_2 Concept Reference
Reference Manual » 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::Convex_hull_traits_adapter_2<R>`
  `CGAL::Projection_traits_xy_3<K>`
  `CGAL::Projection_traits_yz_3<K>`
  `CGAL::Projection_traits_xz_3<K>`

## 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.
typedef unspecified_type | Less_xy_2
| Binary predicate object type comparing `Point_2`s lexicographically.
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 | Compare_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 compares the signed distance of \( r\) and \( s\) to the directed line \( l_{pq}\) through \( p\) and \( q\).
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\).
typedef unspecified_type | Orientation_2
| Predicate object type that must provide `Orientation operator()(Point_2 e, Point_2 p,Point_2 q)`, that returns `CGAL::LEFT_TURN`, if `r` lies to the left of the oriented line `l` defined by `p` and `q`, returns `CGAL::RIGHT_TURN` if `r` lies to the right of `l`, and returns `CGAL::COLLINEAR` if `r` lies on `l`.

## 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 ()
Compare_signed_distance_to_line_2 | compare_signed_distance_to_line_2_object ()
Less_rotate_ccw_2 | less_rotate_ccw_2_object ()
Left_turn_2 | left_turn_2_object ()
Orientation_2 | orientation_2_object ()

## Member Typedef Documentation

## ◆ Compare_signed_distance_to_line_2

typedef unspecified_type ConvexHullTraits_2::Compare_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 compares the signed distance of \( r\) and \( s\) to the directed line \( l_{pq}\) through \( p\) and \( q\).

It is used to compute the point right of a line with maximum unsigned distance to the line.

## ◆ Equal_2

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.

## ◆ Less_rotate_ccw_2

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!

## ◆ Less_xy_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.