CGAL 4.12  2D Arrangements

#include <CGAL/Arr_polycurve_traits_2.h>
Note: The SubcurveTraits_2
can comprise of Line_segments, Conic_arcs, Circular_arc, Bezier_curves, or Linear_curves.
A portion or a part of any of the above mentioned geometric traits is called a subcurve.
The traits class Arr_polycurve_traits_2
handles piecewise curves that are not necessarily linear, such as conic arcs, circular arcs, Bezier curves, or line segments. We call such a compound curve a polycurve. A polycurve is a chain of subcurves, where each two neighboring subcurves in the chain share a common endpoint; that is, the polycurve is continuous. Furthermore, the target of the \(i\)th segement of a polycurve has to coincide with the source of the \(i+1\)st segment; that is, the polycurve has to be welloriented. Note that it is possible to construct general polycurves that are neither continuous nor welloriented, as it is impossible to enforce this precondition (using the set of predicates required by the relevant concepts, see below). However, such polycurves cannot be used for the actual computation of arrangements. The traits class template exploits the functionality of the SubcurveTraits_2
templateparameter to handle the subcurves that compose the polycurve.
The type substituting the template parameter SubcurveTraits_2
when the template Arr_polycurve_traits_2 is instantiated must be a model of the concepts
If, in addition, the SubcurveTraits_2 models the concept ArrangementApproximateTraits_2
then Arr_polycurve_traits_2
models this concept as well. The same holds for the concept ArrangementOpenBoundaryTraits_2
. If no type is provided, then Arr_segment_traits_2
(instantiated with Exact_predicates_exact_constructions_kernel
as the kernel) is used. Otherwise, Arr_algebraic_segment_traits_2<Coefficient>
, Arr_Bezier_curve_traits_2<RatKernel, AlgKernel, NtTraits>
, Arr_circle_segment_traits_2<Kernel>
, Arr_conic_traits_2<RatKernel, AlgKernel, NtTraits>
, Arr_linear_traits_2<Kernel>
, Arr_non_caching_segment_traits_2<Kernel>
, Arr_segment_traits_2<Kernel>
, Arr_rational_function_traits_2<AlgebraicKernel_d_1>
, or any other model of the concepts above can be used.
The number type used by the injected subcurve 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 polycurve that comprises \(n > 0\) subcurves has \( n+1 \) subcurve endpoints, and they are represented as objects of type SubcurveTraits_2::Point_2
. Since the notion of a vertex is reserved to 0dimensional elements of an arrangement, we use, in this context, the notion of points in order to refer to the vertices of a polycurve. For example, an arrangement induced by a single nonself intersecting polycurve has exactly two vertices regardless of the number of subcurve endpoints. Finally, the types Subcurve_2
and X_monotone_subcurve_2
nested in Arr_polycurve_traits_2
are nothing but SubcurveTraits_2::Curve_2
and SubcurveTraits_2::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_polycurve_traits_2
which in that version was called Arr_polyline_tratis_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 righttoleft or lefttoright. If you wish to maintain a lefttoright orientations of the \(x\)monotone polycurve, set the macro CGAL_ALWAYS_LEFT_TO_RIGHT
to 1 before any CGAL header is included.
ArrangementDirectionalXMonotoneTraits_2
ArrangementApproximateTraits_2
(if the type that substitutes the template parameter SubcurveTraits_2
models the concept as well)
Arr_algebraic_segment_traits_2<Coefficient>
Arr_Bezier_curve_traits_2<RatKernel, AlgKernel, NtTraits>
Arr_circle_segment_traits_2<Kernel>
Arr_conic_traits_2<RatKernel, AlgKernel, NtTraits>
Arr_linear_traits_2<Kernel>
Arr_non_caching_segment_traits_2<Kernel>
Arr_segment_traits_2<Kernel>
Arr_rational_function_traits_2<AlgebraicKernel_d_1>
CGAL_ALWAYS_LEFT_TO_RIGHT
Classes  
class  Construct_curve_2 
Construction functor of a general (not necessarily \(x\)monotone) polycurve. More...  
class  Construct_x_monotone_curve_2 
Construction functor of \(x\)monotone polycurve. More...  
class  Curve_2 
The Curve_2 type nested in the Arr_polycurve_traits_2 represents general continuous piecewiselinear subcurves (a polycurve can be selfintersecting) and support their construction from range of subcurves. More...  
class  Make_x_monotone_2 
Subdivide the given subcurve into xmonotone subcurves and insert them into the given output iterator. More...  
class  Number_of_points_2 
Function object which returns the number of subcurve endpoints of a polycurve. More...  
class  Push_back_2 
Functor to augment a polycurve by either adding a vertex or a subcurve at the back. More...  
class  Push_front_2 
Functor to augment a polycurve by either adding a vertex or a subcurve at the front. More...  
class  Trim_2 
class  X_monotone_curve_2 
The X_monotone_curve_2 class nested within the polycurve traits is used to represent \( x\)monotone piecewise linear subcurves. More...  
Types  
typedef SubcurveTraits_2::Point_2  Point_2 
typedef SubcurveTraits_2::Curve_2  Subcurve_2 
typedef SubcurveTraits_2::X_monotone_curve_2  X_monotone_subcurve_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 