|
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, |
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>
| 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
| |
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. |
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. |
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.
| ||||
| int | s.arcno () const |
returns the arc number of the segment.
| ||
| Algebraic_real_1 | s.x () const |
returns the x-coordinate of a vertical segment.
| ||
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.
| 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. |
| 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.
| ||||
| 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
| ||||
| 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) | ||
| 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.
| ||||
| 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.
| ||||
| 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.
| ||||