CGAL 6.1 - 2D Arrangements

Loading...
Searching...
No Matches
List of all members | Classes
CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits > Class Template Reference
Reference Manual » Geometry Traits Classes

`#include <CGAL/Arr_conic_traits_2.h>`

## Definition

template<typename RatKernel, typename AlgKernel, typename NtTraits>
class CGAL::Arr_conic_traits_2< RatKernel, AlgKernel, NtTraits >

The class `Arr_conic_traits_2` is a model of the `AosTraits_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 substituted by 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 substituting the `CORE_algebraic_number_traits` class for the `NtTraits` parameter, and the `Cartesian<NtTraits::Rational>` and `Cartesian<NtTraits::Algebraic>` instances for 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 `AosDirectionalXMonotoneTraits_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.

Is model of
  `AosTraits_2`
  `AosLandmarkTraits_2`
  `AosApproximateTraits_2`
  `AosDirectionalXMonotoneTraits_2`

Types

## Classes
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 conic-arc traits can represent arbitrary conic arcs and support their construction in various ways. More...
class | Point_2
| The `Point_2` class nested within the conic-arc 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 conic-arc 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 for, e.g., the landmarks point-location strategy and the drawing function.
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
| obtains a `Construct_curve_2` functor.
Construct_x_monotone_curve_2 | construct_x_monotone_curve_2_object () const
| obtains a `Construct_x_monotone_curve_2` functor.
Construct_bbox_2 | construct_bbox_2_object () const
| obtains a `Bbox_2` functor.
Trim_2 | trim_2_object () const
| obtains a `Trim_2` functor.