\( \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 Arrangements
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Arr_polyline_traits_2< SegmentTraits > Class Template Reference

#include <CGAL/Arr_polyline_traits_2.h>

Definition

The traits class Arr_polyline_traits_2 handles piecewise linear curves, commonly referred to as polylines.

Each polyline is a chain of segments, where each two neighboring segments in the chain share a common endpoint; that is, the polyline is continuous. Furthermore, the target of the \(i\)th segement of a polyline has to coincide with the source of the \(i+1\)st segment; that is, the polyline has to be well-oriented. Note that it is possible to construct general polylines that are neither continuous nor well-oriented, as it is impossible to enforce this precondition (using the set of predicates required by the relevant concepts, see below). However, such polylines cannot be used for the actual computation of arrangements. The traits class template exploits the functionality of the SegmentTraits template-parameter to handle the segments that compose the polyline curves.

The type substituting the template parameter SegmentTraits when the template Arr_polyline_traits_2 is instantiated must be a model of the concepts

If, in addition, the segment traits models the concept ArrangementLandmarkTraits_2 then Arr_polyline_traits_2 models this concept as well. If no type is provided, then Arr_segment_traits_2 (instantiated with Exact_predicates_exact_constructions_kernel as the kernel) is used. Otherwise, Arr_segment_traits_2<Kernel> or Arr_non_caching_segment_traits_2<Kernel> can be used, where the first alternative is recommended.

The number type used by the injected segment traits should support exact rational arithmetic (that is, the number type should support the arithmetic operations \( +\), \( -\), \( \times\) and \( \div\) carried out without loss of precision), in order to avoid robustness problems, although other inexact number types could be used at the user's own risk.

A polyline that comprises \(n > 0\) segments has \( n+1 \) points, and they are represented as objects of type SegmentTraits::Point_2. Since the notion of a vertex is reserved to 0-dimensional elements of an arrangement, we use, in this context, the notion of points in order to refer to the vertices of a polyline. For example, an arrangement induced by a single non-self intersecting polyline has exactly two vertices regardless of the number of points. Finally, the types Segment_2 and X_monotone_segment_2 nested in Arr_polyline_traits_2 are nothing but SegmentTraits::Curve_2 and SegmentTraits::X_monotone_curve_2, respectively.

A note on Backwards compatibility
In CGAL version 4.2 (and earlier) any object of the X_monotone_curve_2 type nested in Arr_polyline_traits_2 maintained a direction invariant; namely, its vertices were ordered in an ascending lexicographical \((xy)\)-order. This restriction is no longer imposed and X_monotone_curve_2 can be now directed either from right-to-left or left-to-right. If you wish to maintain a left-to-right orientations of the \(x\)-monotone polylines, set the macro CGAL_ALWAYS_LEFT_TO_RIGHT to 1 before any CGAL header is included.

Is Model Of:

ArrangementTraits_2

ArrangementLandmarkTraits_2 (if the template parameter SegmentTraits models the concept as well)

ArrangementDirectionalXMonotoneTraits_2

See Also
Arr_segment_traits_2<Kernel>
Arr_non_caching_segment_traits_2<Kernel>
CGAL_ALWAYS_LEFT_TO_RIGHT
Examples:
Arrangement_on_surface_2/generic_curve_data.cpp, and Arrangement_on_surface_2/polylines.cpp.

Classes

class  Construct_curve_2
 Construction functor of a general (not necessarily \(x\)-monotone) polyline. More...
 
class  Construct_x_monotone_curve_2
 Construction functor of \(x\)-monotone polyline. More...
 
class  Curve_2
 The Curve_2 type nested in the Arr_polyline_traits_2 represents general continuous piecewise-linear curves (a polyline can be self-intersecting) and support their construction from range of segments. More...
 
class  Make_x_monotone_2
 Cut the given curve into x-monotone sub-curves and insert them into the given output iterator. More...
 
class  Number_of_points_2
 Function object which returns the number of points of a polyline. More...
 
class  Push_back_2
 Functor to augment a polyline by either adding a vertex or a segment at the back. More...
 
class  Push_front_2
 Functor to augment a polyline by either adding a vertex or a segment at the front. More...
 
class  X_monotone_curve_2
 The X_monotone_curve_2 class nested within the polyline traits is used to represent \( x\)-monotone piecewise linear curves. More...
 

Types

typedef SegmentTraits::Point_2 Point_2
 
typedef SegmentTraits::Curve_2 Segment_2
 
typedef
SegmentTraits::X_monotone_curve_2 
X_monotone_segment_2
 

Accessing Functor Objects

Construct_curve_2 construct_curve_2_object () const
 
Construct_x_monotone_curve_2 construct_x_monotone_curve_2_object () const
 
Number_of_points_2 number_of_points_2_object () const
 
Push_back_2 push_back_2_object () const
 
Push_front_2 push_front_2_object () const
 
Make_x_monotone_2 make_x_monotone_2_object () const