CGAL 5.6  2D Arrangements

#include <CGAL/Arr_conic_traits_2.h>
The class Arr_conic_traits_2
is a model of the ArrangementTraits_2
concept and can be used to construct and maintain arrangements of bounded segments of algebraic curves of degree \(2\) at most, also known as conic curves.
A general conic curve \(C\) is the locus of all points \((x,y)\) satisfying the equation: \(r x^2 + s y^2 + t x y + u x + v y + w = 0\), where:
If \(4 r s  t^2 > 0\), \( C\) is an ellipse. A special case occurs when \(r = s\) and \( t = 0\), when \( C\) becomes a circle.
If \(4 r s  t^2 < 0\), \( C\) is a hyperbola.
If \(4 r s  t^2 = 0\), \( C\) is a parabola. A degenerate case occurs when \(r = s = t = 0\), when \( C\) is a line.
A bounded conic arc is defined as either of the following:
A full ellipse (or a circle) \( C\).
The tuple \( \langle C, p_s, p_t, o \rangle\), where \( C\) is the supporting conic curve, with the arc endpoints being \( p_s\) and \( p_t\) (the source and target points, respectively). The orientation \( o\) indicates whether we proceed from \( p_s\) to \( p_t\) in a clockwise or in a counterclockwise direction. Note that \( C\) may also correspond to a line or to pair of lines—in this case \( o\) may specify a COLLINEAR
orientation.
A very useful subset of the set of conic arcs are line segments and circular arcs, as arrangements of circular arcs and line segments have some interesting applications (e.g., offsetting polygons and motion planning for a disc robot). Circular arcs and line segment are simpler objects and can be dealt with more efficiently than arbitrary arcs. Indeed, it is possible to construct conic arcs from segments and from circles. Using these constructors is highly recommended: It is more straightforward and also expedites the arrangement construction. However, in case the set of input curves contain only circular arcs and line segments, it is recommended using the Arr_circle_segment_2
class to achieve better running times.
In our representation, all conic coefficients (namely \(r, s, t, u, v, w\)) must be rational numbers. This guarantees that the coordinates of all arrangement vertices (in particular, those representing intersection points) are algebraic numbers of degree \(4\) (a real number \(\alpha\) is an algebraic number of degree \(d\) if there exist a polynomial \( p\) with integer coefficient of degree \(d\) such that \(p(\alpha) = 0\)). We therefore require separate representations of the curve coefficients and the point coordinates. The NtTraits
should be instantiated with a class that defines nested Integer
, Rational
, and Algebraic
number types and supports various operations on them, yielding certified computation results (for example, it can convert rational numbers to algebraic numbers and can compute roots of polynomials with integer coefficients). The other template parameters, RatKernel
and AlgKernel
should be geometric kernels instantiated with the NtTraits::Rational
and NtTraits::Algebraic
number types, respectively. It is recommended instantiating the CORE_algebraic_number_traits
class as the NtTraits
parameter, with Cartesian<NtTraits::Rational>
and Cartesian<NtTraits::Algebraic>
instantiating the two kernel types, respectively. The number types in this case are provided by the Core library, with its ability to exactly represent simple algebraic numbers.
The traits class inherits its point type from AlgKernel::Point_2
, and defines a curve and \(x\)monotone curve types, as detailed below.
While the Arr_conic_traits_2
models the concept ArrangementDirectionalXMonotoneTraits_2
, the implementation of the Are_mergeable_2
operation does not enforce the input curves to have the same direction as a precondition. Moreover, Arr_conic_traits_2
supports the merging of curves of opposite directions.
Types
Classes  
class  Approximate_2 
A functor that approximates a point and an \(x\)monotone curve. More...  
class  Construct_bbox_2 
A functor that constructs a bounding box of a conic arc. More...  
class  Construct_curve_2 
A functor that constructs a conic arc. More...  
class  Construct_x_monotone_curve_2 
A functor that constructs an \(x\)monotone conic arc. More...  
class  Curve_2 
The Curve_2 class nested within the conicarc traits can represent arbitrary conic arcs and support their construction in various ways. More...  
class  Point_2 
The Point_2 class nested within the conicarc traits is used to represent points. More...  
class  Trim_2 
A functor that trims a conic arc. More...  
class  X_monotone_curve_2 
The X_monotone_curve_2 class nested within the conicarc traits is used to represent \(x\)monotone conic arcs. More...  
Types  
typedef unspecified_type  Rational 
the NtTraits::Rational type (and also the RatKernel::FT type).  
typedef unspecified_type  Algebraic 
the NtTraits::Algebraic type (and also the AlgKernel::FT type).  
Auxiliary Functor definitions, used gor, e.g., the landmarks  
typedef double  Approximate_number_type 
typedef CGAL::Cartesian< Approximate_number_type >  Approximate_kernel 
typedef Approximate_kernel::Point_2  Approximate_point_2 
Accessing Functor Objects  
Construct_curve_2  construct_curve_2_object () const 
Obtain a Construct_curve_2 functor. More...  
Construct_x_monotone_curve_2  construct_x_monotone_curve_2_object () const 
Obtain a Construct_x_monotone_curve_2 functor. More...  
Construct_bbox_2  construct_bbox_2_object () const 
Obtain a Bbox_2 functor. More...  
Trim_2  trim_2_object () const 
Obtain a Trim_2 functor. More...  
Trim_2  approximate_2_object () const 
Obtain an Approximate_2 functor. More...  
Trim_2 CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >::approximate_2_object  (  )  const 
Obtain an Approximate_2
functor.
Construct_bbox_2 CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >::construct_bbox_2_object  (  )  const 
Obtain a Bbox_2
functor.
Construct_curve_2 CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >::construct_curve_2_object  (  )  const 
Obtain a Construct_curve_2
functor.
Construct_x_monotone_curve_2 CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >::construct_x_monotone_curve_2_object  (  )  const 
Obtain a Construct_x_monotone_curve_2
functor.
Trim_2 CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >::trim_2_object  (  )  const 
Obtain a Trim_2
functor.