\( \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.13 - 2D Convex Hulls and Extreme Points
List of all members
ConvexHullTraits_2 Concept Reference
2D Convex Hulls and Extreme Points 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_2s. More...
 
typedef unspecified_type Less_xy_2
 Binary predicate object type comparing Point_2s 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...
 
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 ()
 
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 ()
 
Orientation_2 orientation_2_object ()
 

Member Typedef Documentation

◆ Equal_2

typedef unspecified_type ConvexHullTraits_2::Equal_2

Binary predicate object type comparing Point_2s.

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_signed_distance_to_line_2

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.

◆ Less_xy_2

typedef unspecified_type ConvexHullTraits_2::Less_xy_2

Binary predicate object type comparing Point_2s 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.