\( \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.5 - 2D Polygon Partitioning
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
PartitionTraits_2 Concept Reference

Definition

The polygon partitioning functions are each parameterized by a traits class that defines the primitives used in the algorithms. Many requirements are common to all traits classes. The concept PartitionTraits_2 defines this common set of requirements.

Has Models:
CGAL::Partition_traits_2<R>
See Also
CGAL::approx_convex_partition_2()
CGAL::greene_approx_convex_partition_2()
CGAL::optimal_convex_partition_2()
CGAL::y_monotone_partition_2()

Types

typedef unspecified_type Point_2
 The point type on which the partitioning algorithm operates.
 
typedef unspecified_type Polygon_2
 The polygon type to be created by the partitioning algorithm. More...
 
typedef unspecified_type Less_xy_2
 Predicate object type that compares 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 provides 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 Orientation_2
 Predicate object type that provides CGAL::Orientation operator()(Point_2 p, Point_2 q, Point_2 r) 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\).
 
typedef unspecified_type Compare_y_2
 Predicate object type that provides CGAL::Comparision_result operator()(Point_2 p, Point_2 q) to compare the \( y\) values of two points. More...
 
typedef unspecified_type Compare_x_2
 The same as Compare_y_2, except that \( x\) coordinates are compared instead of \( y\).
 

Creation

A copy constructor and default constructor are required.

 PartitionTraits_2 ()
 
 PartitionTraits_2 (PartitionTraits_2 tr)
 

Operations

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

Less_yx_2 less_yx_2_object () const
 
Less_xy_2 less_xy_2_object () const
 
Left_turn_2 left_turn_2_object () const
 
Orientation_2 orientation_2_object () const
 
Compare_y_2 compare_y_2_object () const
 
Compare_x_2 compare_x_2_object () const
 

Member Typedef Documentation

Predicate object type that provides CGAL::Comparision_result operator()(Point_2 p, Point_2 q) to compare the \( y\) values of two points.

The operator must return CGAL::SMALLER if \( p_y < q_y\), CGAL::LARGER if \( p_y > q_y\) and CGAL::EQUAL if \( p_y = q_y\).

Predicate object type that compares 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 the \( x\) and \( y\) coordinates of point \( p\), respectively.

The polygon type to be created by the partitioning algorithm.

For testing the validity postcondition of the partition, this type should provide a nested type Vertex_const_iterator that is the type of the iterator over the polygon vertices and member functions Vertex_const_iterator vertices_begin() and Vertex_const_iterator vertices_end().