ConvexHullTraits

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

ConvexHullTraits_2

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.

Types

ConvexHullTraits_2::Point_2
	The point type on which the convex hull functions operate.

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.

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<_xyq, 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.

ConvexHullTraits_2::Less_yx_2
	Same as Less_xy_2 with the roles of x and y interchanged.

ConvexHullTraits_2::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.

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.

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!

Creation

Only a copy constructor is required.

ConvexHullTraits_2 traits ( & t);

Operations

The following member functions to create instances of the above predicate object types must exist.

Equal_2	traits.equal_2_object ()
Less_xy_2	traits.less_xy_2_object ()
Less_yx_2	traits.less_yx_2_object ()
Less_signed_distance_to_line_2	traits.less_signed_distance_to_line_2_object ()
Less_rotate_ccw_2	traits.less_rotate_ccw_2_object ()
Left_turn_2	traits.left_turn_2_object ()

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_zx_3<K>

CGAL::Convex_hull_projective_xy_traits_2<Point_3>
CGAL::Convex_hull_projective_xz_traits_2<Point_3>
CGAL::Convex_hull_projective_yz_traits_2<Point_3>