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.

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_2s.

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_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.

Definition

Types

Creation

Operations

Member Typedef Documentation