Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
Class

CGAL::Arr_algebraic_segment_traits_2<Coefficient>

Definition

The traits class Arr_algebraic_segment_traits_2<Coefficient> is a model of the ArrangementTraits_2 concept that handles planar algebraic curves of arbitrary degree, and x-monotone of such curves. A planar (real) algebraic curve is the vanishing set of a polynomial in two variables, that is, the curve is defined by the defining equation

f(x):=∑i+j ≤ n aij xi yj =0,
where n is the degree of the curve.

The traits class allows the construction of algebraic curves, by specifying their implicit equation. x-monotone and vertical segments of a curve can also be defined; unbounded curves and segments are supported. The template parameter Coefficient defines the innermost coefficient type of the polynomials. Currently, the types leda::integer and CORE::BigInt are supported as well as any instance of CGAL::Sqrt_extension that is instantiated with one of the integral types above.

#include <CGAL/Arr_algebraic_segment_traits_2.h>

Is Model for the Concepts

ArrangementTraits_2

Types

Arr_algebraic_segment_traits_2<Coefficient>::enum Site_of_point { POINT_IN_INTERIOR = 0, MIN_ENDPOINT = -1, MAX_ENDPOINT = 1 };
Value to specify whether a point should be in the interior of a segment, or its minimal point, or its maximal point in lexicographic order.


Arr_algebraic_segment_traits_2<Coefficient>::Polynomial_2
the type for bivariate polynomials, with innermost coefficient type Coefficient. Constitutes a model of the concept Polynomial_d with two variables. (see page )


Arr_algebraic_segment_traits_2<Coefficient>::Algebraic_kernel_1
model for the concept AlgebraicKernel_1


Arr_algebraic_segment_traits_2<Coefficient>::Algebraic_real_1
represents coordinates of points. Typedef from Algebraic_kernel_1::Algebraic_real_1


Arr_algebraic_segment_traits_2<Coefficient>::Bound
Typedef from Algebraic_kernel_1::Bound

Class Arr_algebraic_segment_traits_2<Coefficient>::Curve_2

Models the ArrangementTraits_2::Curve_2 concept. Represents algebraic curves. Internally, the type stores topological-geometric information about the particular curve. In order to use internal caching, instances should only be created using the Construct_curve_2 functor of the traits class.

Polynomial_2 C.polynomial () const returns the defining polynomial of the curve.

Class Arr_algebraic_segment_traits_2<Coefficient>::Point_2

Models the ArrangementBasicTraits_2::Point_2 concept. Represents points in ℝ2. Intersection points of algebraic curves are in general non-rational, so we need a data structure that is capable of representing arbitrary points with algebraic coordinates.

The traits class represents algebraic coordinates by the type Algebraic_real_1, which is a model of the AlgebraicReal_1 concept. A point p is stored by a triple (x,cv,arcno), where x is the x-coordinate of a point, cv is an instance of Curve_2 that contains the point, (and has no vertical line at x), and arcno is an int, denoting that p is met as the arcno-th point when shooting a vertical ray at x, starting from -∞ (where counting starts with 0).

In addition to the methods listed below, the copy constructor and assignment operator for Point_2 objects are also supported.

The functor Construct_point_2 constructs Point_2 instances.

Algebraic_real_1 p.x () const returns the x-coordinate of p.

Algebraic_real_1 p.y () const returns the y-coordinates of p.
Attention: As described above, points are not stored by their y-coordinate in Algebraic_real_1 representation. In fact, this representation must be computed on demand, and might become quite costly for points defined by high-degree polynomials. Therefore, it is recommended to avoid to call this function as much as possible.

Curve_2 p.curve () const returns a Curve_2 instance that pis part of.

int p.arcno () const returns the arc number of p.

std::pair<double,double> p.to_double () const returns double-approximations of the x- and y-coordinates.

Class Arr_algebraic_segment_traits_2<Coefficient>::X_monotone_curve_2

Models the ArrangementBasicTraits_2::X_monotone_curve_2 concept. Represents terminal segments of an algebraic curves, that means vertical segments or x-monotone segments with no critical x-coordinate in the interior of their x-range. Terminal segments might either be bounded or unbounded. By definition, each interior point of a non-vertical segment has the same arc number (see the documentation of type Point_2 above, which is called the arc number of the segment (note the arc number at the endpoints might differ). Such segments are represented internally by a 4-tuple (p,q,cv,arcno), where p and q are the endpoints, cv is the supporting curve that the segment belongs to, and arcno is the arc number of the segment.

Arbitrary (weakly) x-monotone segments are presented by a range of X_monotone_curve_2 instances, whose union equals the segment. The functor Construct_x_monotone_segment_2 allows their construction. To construct all (maximal) terminal segments of a curve, use the Make_x_monotone_2 functor supplied by the traits class.

Curve_2 s.curve () const returns the supporting algebraic curve of s.

bool s.is_vertical () const returns whether s is a vertical segment.

bool s.is_finite ( CGAL::Arr_curve_end ce) const
returns whether s has a finite endpoint on the left (if ce==CGAL::ARR_MIN_END) or on the right (if ce==CGAL::ARR_MAX_END).

Point_2 s.curve_end ( CGAL::Arr_curve_end ce) const
returns the left or right endpoint of sfor ce==CGAL::ARR_MIN_END and ce==CGAL::ARR_MAX_END.
Precondition: (The corresponding curve end is finite)

int s.arcno () const returns the arc number of the segment.
Precondition: (The segment is non-vertical)

Algebraic_real_1 s.x () const returns the x-coordinate of a vertical segment.
Precondition: (The segment is vertical)

Object Creation Functors

Curves, points, and x-monotone segments are created by special functors. The functors are not default constructible; the only possibility to obtain them is by the corresponding accessing functions.

Class Arr_algebraic_segment_traits_2<Coefficient>::Construct_curve_2

Curve_2 fo ( Polynomial_2 p ) Returns a Curve_2 object that represents the curve defined by the polynomial p

Curve_2 fo ( std::string s ) Returns a Curve_2 object specified by s. The passed string represents the defining polynomial of the curve and must be given in a MAPLE-readable format using "x" as first and "y" as second variable, e.g., "(xˆ3*y-2*x)*(-6*x-yˆ3*xˆ6)" for integer coefficients, and "3/2*x*yˆ4-5/7*xˆ2+3/1" for rational coefficients.

Class Arr_algebraic_segment_traits_2<Coefficient>::Construct_point_2

Point_2 fo ( Algebraic_real_1 x , Curve_2 cv , int arcno )
Returns a Point_2 object that represents the arcno-th point in the fiber of cv at x-coordinate x, counted from the bottom, starting with zero.
Precondition: (cv must not have a vertical line at x, and 0 ≤ arcno < c, where c is the number of points in the fiber of cv at x.)

Point_2 fo ( Algebraic_real_1 x , X_monotone_curve_2 xcv )
Returns a Point_2 object that represents the point on xcv at x-coordinate x
Precondition: (x is in the x-range of xcv.)

Point_2 fo ( Algebraic_real_1 x , Algebraic_real_1 y )
Returns a Point_2 object that represents (x,y)

Point_2 fo ( Coefficient x , Coefficient y )
Returns a Point_2 object that represents (x,y)

Point_2 fo ( Bound x , Bound y ) Returns a Point_2 object that represents (x,y)

Point_2 fo ( int x , int y ) Returns a Point_2 object that represents (x,y)

Class Arr_algebraic_segment_traits_2<Coefficient>::Construct_x_monotone_segment_2

template<class OutputIterator>
OutputIterator fo ( Curve_2 cv , Point_2 end_min , Point_2 end_max , OutputIterator out )
Writes a sequence of X_monotone_curve_2 objects (terminal segments) into out. These terminal segments compose an x-monotone (or vertical) segment of the curve cv that starts in end_min, and ends in end_max.
Precondition: (end_min must have a unique x-monotone segment to its right, or end_max must have a unique x-monotone segment to its left. Furthermore, end_min and end_max must be connected by an x-monotone segment of cv)

template<class OutputIterator>
OutputIterator fo ( Curve_2 cv , Point_2 p , Site_of_point site_of_p , OutputIterator out )
Writes a sequence of X_monotone_curve_2 objects into out. These segments form an x-monotone (or vertical) segment of the curve cv.

If site_of_p==POINT_IN_INTERIOR, the maximal segment is returned that contains p in its interior.

If site_of_p==MIN_ENDPOINT, the maximal segment is returned that contains p as its left endpoint.

If site_of_p==MAX_ENDPOINT, the maximal segment is returned that contains p as its left endpoint.

Precondition: (If site_of_p==POINT_IN_INTERIOR, p must be an interior point of an x-monotone or a vertical segment. If site_of_p==MIN_ENDPOINT, p must either have a unique x-monotone segment to the right, or a vertical segment from p upwards. If site_of_p==MAX_ENDPOINT, p must either have a unique x-monotone segment to the left, or a vertical segment from p downwards.)

template<class OutputIterator>
OutputIterator fo ( Point_2 p , Point_2 q , OutputIterator out )
Writes a sequence of X_monotone_curve_2 objects into out. These segments form a straight-line segment connecting the points p and q. If p and q share the same x-coordinate, the constructed vertical segment consists of only one X_monotone_curve_2 object and can be computed efficiently. In the non-vertical case, the construction is only possible if p and q have both rational x- and y-coordinates.
Precondition: (p must not be equal to q.)

Accessing functor objects

Construct_curve_2 traits.construct_curve_2_object () const
Construct_point_2 traits.construct_point_2_object () const
Construct_x_monotone_segment_2 traits.construct_x_monotone_segment_2_object () const

Next: Arr_curve_data_traits_2<Tr,XData,Mrg,CData,Cnv>
Navigation: Up   Table of Contents   Package Overview   Bibliography   Index   Title   Acknowledging CGAL
CGAL Open Source Project. Release 4.0.2. 4 July 2012.