 CGAL 5.5.2 - 2D Convex Hulls and Extreme Points
ConvexHullTraits_2 Concept Reference

## 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>

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 ()

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

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

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

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.