CGAL 5.6.1  2D Convex Hulls and Extreme Points

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.
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  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\). 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  
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 () 
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.
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.
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!
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.