- the number of components equals a number of your choice, and
- all data points are either on the boundary or in the interior of the regularized version of the \f$ \alpha\f$-shape (no singular edges).
- When using a weighted triangulation (`Regular_triangulation_2`), the vertex and face classes must respectively be models to both `AlphaShapeVertex_2` and `RegularTriangulationVertexBase_2`, and to both `AlphaShapeFace_2` and `RegularTriangulationFaceBase_2` (see example: \ref I1_SectWeightedAS2D).
- When using a periodic triangulation (`Periodic_2_Delaunay_triangulation_2`), the vertex and face classes must respectively be models to both `AlphaShapeVertex_2` and `Periodic_2TriangulationVertexBase_2`, and to both `AlphaShapeFace_2` and `Periodic_2TriangulationFaceBase_2` (see example: \ref AlphaShape_2DExampleForPeriodicAlphaShapes).
- All data points are either on the boundary or in the interior of the regularized version of the alpha shape (no singular faces).
- The number of components is equal or less than a given number.
- When using a weighted triangulation (`Regular_triangulation_3` or `Periodic_3_regular_triangulation_3`), the vertex and cell classes must respectively be models to both `AlphaShapeVertex_3` and `RegularTriangulationVertexBase_3`, and to both `AlphaShapeCell_3` and `RegularTriangulationCellBase_3` (see example: \ref AlphaShape_3DExampleforWeightedAlphaShapes).
- When using a periodic triangulation (`Periodic_3_Delaunay_triangulation_3` or `Periodic_3_regular_triangulation_3`), the vertex and cell classes must respectively be models to both `AlphaShapeVertex_3` and `Periodic_3TriangulationDSVertexBase_3`, and to both `AlphaShapeCell_3` and `Periodic_3TriangulationDSCellBase_3` (see example: \ref AlphaShape_3DExampleForPeriodicAlphaShapes).
- The dimension is \f$ -1\f$ if the Apollonius graph contains no circles.
- The dimension is \f$ 0\f$ if the Apollonius graph contains exactly one visible circle.
- The dimension is \f$ 1\f$ is the Apollonius graph contains exactly two visible circles.
- the geometric traits class. It provides the basic geometric objects involved in the algorithm, such as sites, points etc. It also provides the geometric predicates for the computation of the Apollonius graph, as well as some basic constructions that can be used, for example, to visualize the Apollonius graph or the Apollonius diagram. The geometric traits for the Apollonius graph will be discussed in more detail in the next section.
- the Apollonius graph data structure. This is essentially
the same as the triangulation data structure (discussed in Chapter
\ref Chapter_2D_Triangulation_Data_Structure ), augmented with some
additional operations that are specific to Apollonius graphs. The
corresponding concept is that of
`ApolloniusGraphDataStructure_2`, which in fact is a refinement
of the `TriangulationDataStructure_2` concept. The class
`Triangulation_data_structure_2
| \image html ./apollonius-left_vertex.png \image latex ./apollonius-left_vertex.png | \image html ./apollonius-right_vertex.png \image latex ./apollonius-right_vertex.png |
| \image html ./apollonius-no_conflict.png \image latex ./apollonius-no_conflict.png | \image html ./apollonius-entire_edge.png \image latex ./apollonius-entire_edge.png |
| \image html ./apollonius-interior.png \image latex ./apollonius-interior.png | \image html ./apollonius-both_vertices.png \image latex ./apollonius-both_vertices.png |
- From the complexity-bound perspective, most of the arrangements that we can deal with can be regarded as defined by well-behaved curves. Even though the package allows for self-intersecting curves, for most types each curve can be decomposed into a constant number of well-behaved curves, thus having no effect on the asymptotic bounds that we state.
- One type of curves that we deal with is special in this sense: polylines, namely concatenations of an unlimited number of line segments; see Section \ref arr_sssectr_polylines. A polyline is not well behaved, as it cannot be decomposed into a constant number of constant-descriptive complexity subcurves. Informative bounds for arrangements of polylines are expressed by other parameters in addition to the number of polylines, for example, the total number of segments in all the polylines together. The same holds for the more general type polycurve, which are piecewise curves that are not necessarily linear; see Section \ref arr_sssectr_polycurves.
- the separation of the representation of the arrangements and the various geometric algorithms that operate on them, and
- the separation of the topological and geometric aspects of the two-dimensional subdivision.
- The `Traits` template-parameter should be substituted by a model of the `AosBasicTraits_2` concept and optionally additional geometry traits concepts. A model of the `AosBasicTraits_2` concept defines the types of \f$x\f$-monotone curves and two-dimensional points, namely `AosBasicTraits_2::X_monotone_curve_2` and `AosBasicTraits_2::Point_2`, respectively, and supports basic geometric predicates on them. The instantiated traits class determines the family of planar curves that induce the arrangement. In this section we always use `Arr_non_caching_segment_traits_2` as our traits-class model in order to construct arrangements of line segments. In succeeding sections we also use `Arr_segment_traits_2` as our traits-class model. These two traits trade computation time and storage space. The latter stores the underlying line of every segment of the arrangement to expedite certain operations on the arrangement segments. In Section \ref aos_sec-unbounded we use `Arr_linear_traits_2` to construct arrangements of linear curves (i.e., lines, rays, and line segments). The \ref PkgArrangementOnSurface2 package contains several other traits classes that can handle other types of curves, such as polylines (continuous piecewise-linear curves), conic arcs, and arcs of rational functions. We exemplify the usage of these traits classes in Section \ref aos_sec-geom_traits.
- The `Dcel` template-parameter should be substituted by a class
that models the `AosDcel` concept, which is used to represent
the topological layout of the arrangement. This parameter is
substituted by `Arr_default_dcel
` by default, and we use this default value in this and in the following three sections. However, in many applications it is necessary to extend the \dcel features. This is done by substituting the `Dcel` parameter with a different type (typically, a different instance of the `Arr_dcel<>` class template); see Section \ref arr_ssecex_dcel for further explanations and examples.
- \link Arrangement_on_surface_2::Halfedge::curve() `e->curve()`\endlink is equivalent to \link Arrangement_on_surface_2::Halfedge::curve() `e->twin()->curve()`\endlink,
- \link Arrangement_on_surface_2::Halfedge::source() `e->source()`\endlink is equivalent to \link Arrangement_on_surface_2::Halfedge::target() `e->twin()->target()`\endlink, and
- \link Arrangement_on_surface_2::Halfedge::target() `e->target()`\endlink is equivalent to \link Arrangement_on_surface_2::Halfedge::source() `e->twin()->source()`\endlink.
- You can obtain a pair of iterators of type \link Arrangement_on_surface_2::Face::Hole_iterator `Hole_iterator`\endlink that define the range of holes inside a face \f$f\f$ by calling \link Arrangement_on_surface_2::Face::holes_begin() `f->holes_begin()`\endlink and \link Arrangement_on_surface_2::Face::holes_end() `f->holes_end()`\endlink. The value type of this iterator type is \link Arrangement_on_surface_2::Ccb_halfedge_circulator `Ccb_halfedge_circulator`\endlink, defining the CCB that winds in a clockwise order around a hole. The call \link Arrangement_on_surface_2::Face::number_of_holes() `f->number_of_holes()`\endlink return the number of holes in \f$f\f$.
- The calls \link Arrangement_on_surface_2::Face::isolated_vertices_begin() `f->isolated_vertices_begin()`\endlink and \link Arrangement_on_surface_2::Face::isolated_vertices_end() `f->isolated_vertices_end()`\endlink return iterators of type \link Arrangement_on_surface_2::Isolated_vertex_iterator `Isolated_vertex_iterator`\endlink that define the range of isolated vertices inside the face \f$f\f$. The value type of this iterator is \link Arrangement_on_surface_2::Vertex `Vertex`\endlink.
- Neither curve endpoints correspond to any existing arrangement vertex. In this case we have to create two new vertices that correspond to the curve endpoints, respectively, and connect them using a pair of twin halfedges. This halfedge pair forms a new hole inside the face that contains the curve in its interior.
- Exactly one endpoint corresponds to an existing arrangement vertex. (We distinguish between a vertex that corresponds to the left endpoint of the inserted curve and a vertex that corresponds to its right endpoint.) In this case we have to create a new vertex that corresponds to the other endpoint of the curve and to connect the two vertices by a pair of twin halfedges that form an "antenna" emanating from the boundary of an existing connected component. (Note that if the existing vertex is isolated, we need to form a new hole inside the face that contains this vertex, essentially falling back to the handling of the previous case, naturally, skipping the creation of the existing vertex.)
- Both endpoints correspond to existing arrangement vertices. In
this case we connect these vertices using a pair of twin halfedges.
(If one or both vertices are isolated, we fall back to the handling of
the first or second case, respectively, naturally, skipping the
creation of the existing vertices.) The two following subcases may
occur:
- Two disconnected components are merged into a single connected component (as is the case with the segment \f$s_1\f$ in the figure below).
- A new face, which is split from an existing arrangement face, is created (as is the case with the segment \f$s_2\f$ in the figure below). In this case we also have to examine the holes and isolated vertices in the existing face and move the relevant ones inside the new face.
- \link Arrangement_on_surface_2::insert_in_face_interior() `insert_in_face_interior(c, f)`\endlink returns a handle to the halfedge directed from the left endpoint of \f$c\f$ towards the vertex corresponding to its right endpoint.
- \link Arrangement_on_surface_2::insert_from_left_vertex() `insert_from_left_vertex(c, v)`\endlink and \link Arrangement_on_surface_2::insert_from_right_vertex() `insert_from_right_vertex(c, v)`\endlink each returns a handle to the halfedge, the source of which is the vertex \f$v\f$, and the target of which is the new vertex that has just been created.
- \link Arrangement_on_surface_2::insert_at_vertices() `insert_at_vertices(c, v1, v2)`\endlink returns a handle to the halfedge directed from \f$v_1\f$ to \f$v_2\f$.
| \image html pred_around_vertex.png \image latex pred_around_vertex.png | Assume that the specialized insertion function \link Arrangement_on_surface_2::insert_from_left_vertex() `insert_from_left_vertex(c, v)`\endlink is given a curve \f$c\f$, the left endpoint of which is already associated with a non-isolated vertex \f$v\f$. Namely, \f$v\f$ has already several incident halfedges. It is necessary in this case to locate the exact place for the new halfedge mapped to the inserted new curve \f$c\f$ in the circular list of halfedges incident to \f$v\f$. More precisely, in order to complete the insertion, it is necessary to locate the halfedge \f$e_{\mathrm{pred}}\f$ directed toward \f$v\f$, such that \f$c\f$ is located between the curves associated with \f$e_{\mathrm{pred}}\f$ and the next halfedge in the clockwise order in the circular list of halfedges around \f$v\f$; see \cgalFigureRef{aos_fig-insert}. This search may take \cgalBigO{d} time, where \f$d\f$ is the degree of the vertex \f$v\f$. \cgalFootnote{We can store the handles to the halfedges incident to \f$v\f$ in an efficient search structure to obtain \cgalBigO{\log d} access time. However, as \f$d\f$ is usually very small, this may lead to a waste of storage space without a meaningful improvement in running time in practice.} However, if the halfedge \f$e_{\mathrm{pred}}\f$ is known in advance, the insertion can be carried out in constant time, and without performing any geometric comparisons. |
- `Arr_naive_point_location
` employs the naive strategy. It locates the query point naively, exhaustively scanning all arrangement cells. - `Arr_walk_along_line_point_location
` employs the walk-along-a-line (or walk for short) strategy. It simulates a traversal, in reverse order, along an imaginary vertical ray emanating from the query point. It starts from the unbounded face of the arrangement and moves downward toward the query point until it locates the arrangement cell containing it. - `Arr_landmarks_point_location
- `Arr_trapezoid_ric_point_location
` implements an improved variant of Mulmuley's point-location algorithm \cgalCite{m-fppa-90}; see also \cgalCite{bkos-cgaa-00}, Chapter 6. The (expected) query-time is logarithmic in the size of the arrangement. The arrangement faces are decomposed into simpler cells each of constant complexity, known as pseudo trapezoids, and a search structure (a directed acyclic graph) is constructed on top of these cells, facilitating the search of the pseudo trapezoid (hence the arrangement cell) containing a query point in expected logarithmic time. The trapezoidal map and the search structure are built by a randomized incremental construction algorithm (RIC). - `Arr_triangulation_point_location
` uses a constrained triangulation, provided by the \ref PkgTriangulation2 package, as a search structure. Every time the arrangement is modified the constrained triangulation search-structure is reconstructed from scratch, where the edges of the arrangement are set to be the constrained edges of the triangulation. This strategy is inefficient (especially when the number of modifications applied to the arrangement is high) and provided only for educational purposes. - `Arr_walk_along_line_point_location
- If \f$p\f$ is located inside a face, it is inserted as an isolated vertex inside this face.
- If \f$p\f$ lies on an edge, the edge is split to create a vertex associated with \f$p\f$.
- Otherwise,\f$p\f$ coincides with an existing vertex and no further actions are needed.
- `CGAL::insert_non_intersecting_curves<>(arr, begin, end)` inserts a range of \f$x\f$-monotone curves given by the range `[begin, end)` into an arrangement `arr`. The \f$x\f$-monotone curves should be pairwise disjoint in their interior and also interior-disjoint from all existing curves and points of `arr`.
- \link CGAL::insert<>() `insert(arr, begin, end)`\endlink operates on a range of \f$x\f$-monotone curves that may intersect one another.
| Type of Curves | Geometry-Traits Concept | Insertion Function |
|---|---|---|
| \f$x\f$-monotone and pairwise disjoint | `AosBasicTraits_2` or `AosLandmarkTraits_2` | `CGAL::insert_non_intersecting_curve<>()` |
| \f$x\f$-monotone | `AosXMonotoneTraits_2` | `%CGAL::insert<>()` |
| general | `AosTraits_2` | `%CGAL::insert<>()` |
- Cells whose outer boundaries comprise four edges, of which two originate from the original arrangement and the other two are vertical.
- Cells whose outer boundaries comprise three edges, of which two originate from the original arrangement and intersect at a common vertex and the remaining one is vertical.
- Another vertex \f$u\f$ having the same \f$x\f$-coordinate as \f$v\f$.
- An arrangement edge associated with an \f$x\f$-monotone curve that contains \f$v\f$ in its \f$x\f$-range.
- An unbounded face in case \f$v\f$ is incident to an unbounded face, and there is no curve lying above (respectively below) it.
- An empty object, in case \f$v\f$ is the lower (respectively upper) endpoint of a vertical edge in the arrangement.
- \anchor type-normal A vertex, associated with a point in \f$\mathbb{R}^2\f$. Such a vertex always lies inside the bounding rectangle and has bounded coordinates..
- \anchor type-unbounded A vertex that represents an unbounded end of an \f$x\f$-monotone curve that approaches \f$x = -\infty\f$ or at \f$x = \infty\f$. In case of a horizontal line or a curve with a horizontal asymptote, the \f$y\f$-coordinate of the curve end may be finite (see, for example, the vertices \f$v_2\f$ and \f$v_7\f$ in \cgalFigureRef{aos_fig-unb_dcel}), but in general the curve end also approaches \f$y = \pm\infty\f$; see for instance the vertices \f$v_1\f$, \f$v_3\f$, \f$v_6\f$ and \f$v_8\f$ in \cgalFigureRef{aos_fig-unb_dcel}). For convenience, we always take a "tall" enough bounding rectangle and treat such vertices as lying on either the left or the right rectangle edges (that is, if a curve approaches \f$x = -\infty\f$, its left end will be represented by a vertex on the left edge of the bounding rectangle, and if it approaches \f$x = \infty\f$, its right end will be represented by a vertex on the right edge).
- \anchor typeunboundedvertical A vertex that represents the unbounded end of a vertical linear curve (line or ray) or of a curve with a vertical asymptote (finite \f$x\f$-coordinate and an unbounded \f$y\f$-coordinate). Such a vertex always lies on one of the horizontal edges of the bounding rectangle (either the bottom one if \f$y = -\infty\f$, or the top one if \f$y = \infty\f$). The vertices \f$v_4\f$ and \f$v_5\f$ in \cgalFigureRef{aos_fig-unb_dcel} are of this type.
- \anchor typefictitious The fictitious vertices that represent the four corners of the bounding rectangle.
- The calls \link Arrangement_on_surface_2::Vertex::parameter_space_in_x() `v->parameter_space_in_x()`\endlink and \link Arrangement_on_surface_2::Vertex::parameter_space_in_y() `v->parameter_space_in_y()`\endlink determine the location of the geometric embedding of the vertex \f$v\f$. The call \link Arrangement_on_surface_2::Vertex::parameter_space_in_x() `v->parameter_space_in_x()`\endlink returns `CGAL::ARR_INTERIOR` if the \f$x\f$-coordinate associated with \f$v\f$ is finite, `CGAL::ARR_LEFT_BOUNDARY` if \f$v\f$ represents the end of a curve the \f$x\f$-coordinate of which approaches \f$-\infty\f$, and `CGAL::ARR_RIGHT_BOUNDARY` if \f$v\f$ represents the end of a curve the \f$x\f$-coordinate of which approaches \f$\infty\f$. Similarly, the call \link Arrangement_on_surface_2::Vertex::parameter_space_in_y() `v->parameter_space_in_y()`\endlink returns `CGAL::ARR_INTERIOR` if the \f$y\f$-coordinate associated with \f$v\f$ is finite and `CGAL::ARR_BOTTOM_BOUNDARY` or `CGAL::ARR_TOP_BOUNDARY` if \f$v\f$ represents the end of a curve the \f$y\f$-coordinate of which approaches \f$-\infty\f$ or \f$\infty\f$, respectively. The nested \link Arrangement_on_surface_2::Vertex `Vertex`\endlink type also provides the Boolean predicate \link Arrangement_on_surface_2::Vertex::is_at_open_boundary() `is_at_open_boundary()`\endlink. If the call \link Arrangement_on_surface_2::Vertex::is_at_open_boundary() `v->is_at_open_boundary()`\endlink predicates evaluates to `false`, you can access the point associated with \f$v\f$. Otherwise, \f$v\f$ is not associated with a \link Arrangement_on_surface_2::Point_2 `Point_2`\endlink object, as it represents the unbounded end of a curve that approaches infinity.
- The nested \link Arrangement_on_surface_2::Halfedge `Halfedge`\endlink type provides the Boolean predicate \link Arrangement_on_surface_2::Halfedge::is_fictitious `is_fictitious()`\endlink. If the call \link Arrangement_on_surface_2::Halfedge::is_fictitious `e->is_fictitious()`\endlink evaluates to `false`, you can access the \f$x\f$-monotone curve associated with \f$e\f$. Otherwise, \f$e\f$ is not associated with an \link Arrangement_on_surface_2::X_monotone_curve_2 `X_monotone_curve_2`\endlink object.
- The nested \link Arrangement_on_surface_2::Face `Face`\endlink type provides the Boolean predicate \link Arrangement_on_surface_2::Face::is_fictitious() `is_fictitious()`\endlink. The call \link Arrangement_on_surface_2::Face::is_fictitious() `f->is_fictitious()`\endlink evaluates to `true` only when \f$f\f$ lies outside the bounding rectangle. The method \link Arrangement_on_surface_2::Face::outer_ccb() `outer_ccb()`\endlink (see Section \ref arr_sssectr_face must not be invoked for the fictitious face. \cgalFootnote{Typically, the code is guarded against such malicious calls with adequate preconditions. However, these preconditions are suppressed when the code is compiled with maximum optimization.} Note that a valid unbounded face (of an arrangement that supports unbounded curves) has a valid outer CCB, although the CCB comprises only fictitious halfedges if the arrangement is induced only by bounded curves.
| \image html sphere.png | \image html cylinder.png | \image html cone.png | \image html ellipsoid.png | \image html torus.png | \image html paraboloid.png |
| (a) Sphere | (b) Cylinder | (c) Cone | (d) Ellipsoid | (e) Torus | (f) Paraboloid |
- The left side of the boundary of \f$\Phi\f$ consists of the points \f$(x_{\rm min},y)\f$ with \f$y \in {\rm closure}(Y)\f$. It is open, if \f$x_{\rm min} \not\in X\f$ or \f$y\not\in Y\f$, and closed, otherwise. The right side is defined analogously. The bottom side consists of the points \f$(x, y_{\rm min})\f$ with \f$x \notin (x_{\rm min},x_{\rm max})\f$; the top side is defined analogously. The bottom or top sides can also be open. Note that the "corners" of the parameter space belong to the vertical sides; this asymmetry corresponds to the fact that we sweep \f$x\f$-monotone curves, and not \f$y\f$-monotone curves. The four sides together form the boundary \f$\partial \Phi\f$.
- A point \f$p \in S\f$ is regular if it has only one pre-image under \f$\Phi\f$. All pre-images of a non-regular point lie in the boundary of \f$\Phi\f$. In particular, \f$\phi_S\f$ is bijective on \f$(x_{\rm min},x_{\rm max})\times(y_{\rm min},y_{\rm max})\f$. More precisely, a non-regular point has either exactly two pre-images that lie on opposite sides of the domain, or all points of exactly one side of the domain.
| \image html voronoi.jpg | \image html degenerate_voronoi.jpg | \image html power_diagram.jpg | \image html degenerate_power_diagram.jpg |
| (a) | (b) | (c) | (d) |
- The calls \link Arrangement_on_surface_2::Vertex::parameter_space_in_x() `v->parameter_space_in_x()`\endlink and \link Arrangement_on_surface_2::Vertex::parameter_space_in_y() `v->parameter_space_in_y()`\endlink determine the location of the geometric embedding of the vertex \f$v\f$. The call \link Arrangement_on_surface_2::Vertex::parameter_space_in_x() `v->parameter_space_in_x()`\endlink returns `ARR_INTERIOR` if the geometric embedding of \f$v\f$ is a point \f$p\f$ the pre-image of which does not lie on the left nor on the right sides of the boundary of the parameter space. If the left and right sides are not identified, then `ARR_LEFT_BOUNDARY` or `ARR_RIGHT_BOUNDARY` are returned if the pre-image of \f$p\f$ lies on the left or the right side, respectively. If the left and right sides are identified, the return value is unspecified and can be either `ARR_LEFT_BOUNDARY` or `ARR_RIGHT_BOUNDARY`. Similarly, the call \link Arrangement_on_surface_2::Vertex::parameter_space_in_y() `v->parameter_space_in_y()`\endlink returns `ARR_INTERIOR` if the geometric embedding of \f$v\f$ is a point \f$q\f$, the pre-image of which does not lie on the bottom nor on the top sides of the boundary of the parameter space. If the bottom and top sides are not identified, then `ARR_BOTTOM_BOUNDARY` or `ARR_TOP_BOUNDARY` are returned if the pre-image of \f$q\f$ lies on the bottom or the top side, respectively. If the bottom and top sides are identified, the return value is unspecified. If you want to determine whether the pre-image of a point \f$p\f$ lies on identified sides, you need to employ one of the two traits functors \link AosIdentifiedHorizontalTraits_2::Is_on_x_identification_2 `Is_on_x_identification_2`\endlink or \link AosIdentifiedVerticalTraits_2::Is_on_y_identification_2 `Is_on_y_identification_2`\endlink; see Section \ref aos_ssec-traits-curved. If the pre-image of an \f$x\f$-monotone curve \f$c\f$ does not entirely lie on identified sides, you can determine the location of the pre-image of an endpoint of \f$c\f$ employing either the \link AosVerticalSideTraits_2::Parameter_space_in_x_2 `Parameter_space_in_x_2`\endlink functor or the \link AosHorizontalSideTraits_2::Parameter_space_in_y_2 `Parameter_space_in_y_2`\endlink functors; see Section \ref aos_ssec-traits-curved. The operations in both functors accept an enumeration that indicates the curve end, that is, `CGAL::ARR_MIN_END` or `CGAL::ARR_MAX_END`, in addition to the curve itself.
- A face in a planar arrangement has at most one outer CCB. However, an arrangement embedded on a surface may present additional scenarios. For example, a face of an arrangement embedded on a torus may have two outer CCBs, and a face of an arrangement embedded on a sphere might be consider a hole inside the surrounding face or vice versa. To this end, outer CCBs and inner CCBs of faces of arrangements embedded on surfaces are symmetrically treated (while maintaining the invariant that a face always lies to the left of every halfedge of every CCB of the face regardless of whether the CCB is inner or outer). The classification of a CCB as inner or outer becomes an implementation detail. The calls \link Arrangement_on_surface_2::Face::outer_ccbs_begin() `f->outer_ccbs_begin()`\endlink and \link Arrangement_on_surface_2::Face::outer_ccbs_end() `f->outer_ccbs_end()`\endlink return iterators of type \link Arrangement_on_surface_2::Face::Outer_ccb_iterator `Outer_ccb_iterator`\endlink that define a range of outer CCBs inside the face \f$f\f$. Similarly, the methods \link Arrangement_on_surface_2::Face::inner_ccbs_begin() `f->inner_ccbs_begin()`\endlink and \link Arrangement_on_surface_2::Face::inner_ccbs_end() `f->inner_ccbs_end()`\endlink return iterators of type \link Arrangement_on_surface_2::Face::Inner_ccb_iterator `Inner_ccb_iterator`\endlink that define a range of inner CCBs inside the face \f$f\f$. (The latter pair of member functions and the iterator type are equivalent to the methods \link Arrangement_on_surface_2::Face::holes_begin() `holes_begin()`\endlink, \link Arrangement_on_surface_2::Face::holes_end() `holes_end()`\endlink, and \link Arrangement_on_surface_2::Face::Hole_iterator `Hole_iterator`\endlink; see Section \ref arr_sssectr_face.) The calls \link Arrangement_on_surface_2::Face::number_of_outer_ccbs() `f->number_of_outer_ccbs()`\endlink and \link Arrangement_on_surface_2::Face::number_of_inner_ccbs() `f->number_of_inner_ccbs()`\endlink return the number of outer CCBs and the number of inner CCBs in \f$f\f$, respectively.
- \link AosBasicTraits_2::Compare_x_2 `Compare_x_2`\endlink:
- Compares the \f$x\f$-coordinates of two points.
- \link AosBasicTraits_2::Compare_xy_2 `Compare_xy_2`\endlink:
- Compares two points lexicographically, first by their \f$x\f$-coordinates, and if they are equal, by their \f$y\f$-coordinates.
- \link AosBasicTraits_2::Equal_2 `Equal_2`\endlink:
- There are two overloaded Boolean operators that test equality. One returns `true` iff two given points represent the same geometric point in the two-dimensional surface, and the second returns `true` iff the graphs of two given \f$x\f$-monotone curves are the same.\cgalFootnote{The predicate that tests equality between graphs of two \f$x\f$-monotone curves is used only for testing as part of the test suite.}
- \link AosBasicTraits_2::Construct_min_vertex_2 `Construct_min_vertex_2`\endlink:
- Returns the lexicographically smallest (or left) endpoint of an \f$x\f$-monotone curve.
- \link AosBasicTraits_2::Construct_max_vertex_2 `Construct_max_vertex_2`\endlink:
- Returns the lexicographically largest (or right) endpoint of an \f$x\f$-monotone curve.
- \link AosBasicTraits_2::Is_vertical_2 `Is_vertical_2`\endlink:
- Determines whether an \f$x\f$-monotone curve is vertical.
- \link AosBasicTraits_2::Compare_y_at_x_2 `Compare_y_at_x_2`\endlink:
- Given an \f$x\f$-monotone curve \f$c\f$ and a point \f$p\f$ that lies in the \f$x\f$-range of \f$c\f$, determines whether \f$p\f$ is below, above or lies on \f$c\f$.
- \link AosBasicTraits_2::Compare_y_at_x_right_2 `Compare_y_at_x_right_2`\endlink:
- Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common minimal (left) endpoint \f$p\f$, determines whether \f$c_1\f$ is above or below \f$c_2\f$ immediately to the right of \f$p\f$, or whether the two curves overlap there.
- \link AosBasicTraits_2::Do_intersect_2 `Do_intersect_2`\endlink:
- Determines whether two given \f$x\f$-monotone curves intersect. An input flag determines whether the curve are closed or open.
- \link AosBasicTraits_2::Compare_y_at_x_left_2 `Compare_y_at_x_left_2`\endlink:
- Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common maximal (right) endpoint \f$p\f$, determines whether \f$c_1\f$ is above or under \f$c_2\f$ immediately to the left of \f$p\f$, or whether the two curves overlap there.
- \link AosBasicTraits_2::Left_side_category `Left_side_category`\endlink,
- \link AosBasicTraits_2::Right_side_category `Right_side_category`\endlink,
- \link AosBasicTraits_2::Bottom_side_category `Bottom_side_category`\endlink, and
- \link AosBasicTraits_2::Top_side_category `Top_side_category`\endlink.
- \link AosXMonotoneTraits_2::Split_2 `Split_2`\endlink:
- Splits an \f$x\f$-monotone curve \f$c\f$ into two subcurves at a given point \f$p\f$ that lies in the interior of \f$c\f$.
- \link AosXMonotoneTraits_2::Are_mergeable_2 `Are_mergeable_2`\endlink:
- Determines whether two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ that share a common endpoint can be merged into a single continuous \f$x\f$-monotone curve representable by the traits class.\cgalFootnote{On the face of it this seems a difficult predicate to implement. In practice we use very simple tests to decide whether two curves are mergeable: We check whether their underlying curves are identical and whether they do not bend to form a non-\f$x\f$-monotone curve.}
- \link AosXMonotoneTraits_2::Merge_2 `Merge_2`\endlink:
- Merges two mergeable \f$x\f$-monotone curves into a single curve.
- \link AosXMonotoneTraits_2::Intersect_2 `Intersect_2`\endlink:
- Computes all intersection points and overlapping sections of two given \f$x\f$-monotone curves. If possible, computes also the multiplicity of each intersection point. Providing the multiplicity of an intersection point is not required, but it can expedite the arrangement construction. Typically, the multiplicity is a byproduct of the intersection computation. However, if it is not available, undefined multiplicity (coded as 0) is assumed. Having the multiplicity of intersection points while constructing arrangements enables the exploitation of the geometric knowledge intersection points may have.
- \link AosTraits_2::Make_x_monotone_2 `Make_x_monotone_2`\endlink:
- Divides a given general curve of type \link AosTraits_2::Curve_2 `Curve_2`\endlink into continuous weakly \f$x\f$-monotone curves and isolated points.
- \link AosApproximatePointTraits_2::Approximate_2 `Approximate_2`\endlink:
- Given a point `p`, approximate the \f$x\f$ and \f$y\f$-coordinates of `p` using a not necessarily multi-precision number type. We use this operation for approximate computations---there are certain operations performed during the search for the location of the point that need not be exact, and that can be performed faster when carried out, for example, using a fixed-precision number type.
- \link AosConstructXMonotoneCurveTraits_2::Construct_x_monotone_curve_2 `Construct_x_monotone_curve_2`\endlink:
- Given two points \f$p_1\f$ and \f$p_2\f$, construct an \f$x\f$-monotone curve connecting \f$p_1\f$ and \f$p_2\f$.
- \link AosConstructCurveTraits_2::Construct_curve_2 `Construct_curve_2`\endlink:
- Given two points \f$p_1\f$ and \f$p_2\f$, construct a curve connecting \f$p_1\f$ and \f$p_2\f$.
- \link AosApproximateTraits_2::Approximate_2 `Approximate_2`\endlink:
- This operation is overloaded with three versions. The first one returns an approximation of the \f$x\f$- or \f$y\f$-coordinates of a given point as required by the concept `AosApproximatePointTraits_2`; see Section \ref aos_sssec-tr_landmarks_concept. The description of the remaining two follow. (i) Given a point \f$p\f$, obtain an approximation of \f$p\f$, which is an object of type `Approximate_point_2`. This is trivially implemented using the first version. (ii) Given an \f$x\f$-monotone curve \f$c\f$, a small number \f$\epsilon\f$ of type `Approximate_number_type` that serves as an error bound, an output iterator associated with a container of approximate points, and a flag that indicates whether to approximate \f$c\f$ starting from its smallest lexicographic endpoint, compute a polyline that approximates \f$c\f$ in the indicated direction, such that the largest distance between \f$c\f$ and the polyline is not larger than \f$\epsilon\f$. The polyline is represented as a sequence of approximate points.
- `Arr_open_side_tag`
- `Arr_closed_side_tag`
- `Arr_contracted_side_tag`
- `Arr_identified_side_tag`
- `Arr_oblivious_side_tag`
- \link AosVerticalSideTraits_2::Parameter_space_in_x_2 `Parameter_space_in_x_2`\endlink:
- This three-valued predicate is overloaded with two versions as follows: (i) Given a curve \f$c = (x(t), y(t))\f$ and an enumerator that specifies either the minimum end or the maximum end of the curve, and thus maps to a parameter value \f$d \in \{0,1\}\f$, determine the location of the \f$d\f$-end of \f$c\f$ along the \f$x\f$-dimension. Formally, if \f$c\f$ is open at its \f$d\f$-end, determine whether \f$\lim_{t \rightarrow d} x(t)\f$ evaluates to \f$x_{\rm min}\f$, \f$x_{\rm max}\f$, or a value in between. If \f$c\f$ is not open at its \f$d\f$-end, determine whether \f$x(d)\f$ is equal to \f$x_{\rm min}\f$, \f$x_{\rm max}\f$, or a value in between. Return `CGAL::ARR_LEFT_BOUNDARY`, `CGAL::ARR_RIGHT_BOUNDARY`, or `CGAL::ARR_INTERIOR`, accordingly. If \f$c\f$ is vertical and lies on a vertical boundary; that is, either \f$\forall p=(x_p, y_p) \in c\f$ we have \f$x_p = x_{\rm min}\f$ or \f$\forall p=(x_p, y_p) \in c\f$ we have \f$x_p = x_{\rm max}\f$, then the boundary side containing \f$c\f$ cannot be open. (ii) Given a point \f$p=(x_p, y_p)\f$, determine the location of the point with respect to the \f$x\f$-axis. Formally, determine whether \f$x_p\f$ is equal to \f$x_{\rm min}\f$, \f$x_{\rm max}\f$, or a value in between. Return `CGAL::ARR_LEFT_BOUNDARY`, `CGAL::ARR_RIGHT_BOUNDARY`, or `CGAL::ARR_INTERIOR`, accordingly. If \f$p\f$ is on a vertical boundary; that is, \f$x_p \in \{x_{\rm min},x_{\rm max}\}\f$, then the boundary side containing \f$p\f$ cannot be open and must not be identified. In other words, this overloaded version is required only for the concepts `AosClosedLeftTraits_2`, `AosClosedRightTraits_2`, `AosContractedLeftTraits_2` and `AosContractedRightTraits_2`.
- \link AosHorizontalSideTraits_2::Parameter_space_in_y_2 `Parameter_space_in_y_2`\endlink:
- This three-valued predicate is overloaded with two versions as follows: (i) Given a curve \f$c = (x(t), y(t))\f$ and an enumerator that specifies either the minimum end or the maximum end of the curve, and thus maps to a parameter value \f$d \in \{0,1\}\f$, determine the location of the \f$d\f$-end of \f$c\f$ along the \f$y\f$-dimension. Formally, if \f$c\f$ is open at its \f$d\f$-end, determine whether \f$\lim_{t \rightarrow d} y(t)\f$ evaluates to \f$y_{\rm min}\f$, \f$y_{\rm max}\f$, or a value in between. If \f$c\f$ is not open at its \f$d\f$-end, determine whether \f$y(d)\f$ is equal to \f$y_{\rm min}\f$, \f$y_{\rm max}\f$, or a value in between. Return `CGAL::ARR_BOTTOM_BOUNDARY`, `CGAL::ARR_TOP_BOUNDARY`, or `CGAL::ARR_INTERIOR`, accordingly. If \f$c\f$ is horizontal and lies on a horizontal boundary; that is, either \f$\forall p=(x_p, y_p) \in c, y_p = y_{\rm min}\f$ or \f$\forall p=(x_p, y_p) \in c, y_p = y_{\rm max}\f$, then the boundary side containing \f$c\f$ cannot be open and must not be identified. (ii) Given a point \f$p=(x_p, y_p)\f$, determine the location of the point along the \f$y\f$-dimension. Formally, determine whether \f$y_p\f$ is equal to \f$y_{\rm min}\f$, \f$y_{\rm max}\f$, or a value in between. Return `CGAL::ARR_BOTTOM_BOUNDARY`, `CGAL::ARR_TOP_BOUNDARY`, or `CGAL::ARR_INTERIOR`, accordingly. If \f$p\f$ is on a horizontal boundary; that is, \f$y_p \in \{y_{\rm min},y_{\rm max}\}\f$, then the boundary side containing \f$p\f$ cannot be open and must not be identified. In other words, this overloaded version is required only for the concepts `AosClosedBottomTraits_2`, `AosClosedTopTraits_2`, `AosContractedBottomTraits_2` and `AosContractedTopTraits_2`.
- \link AosIdentifiedVerticalTraits_2::Compare_y_on_boundary_2 `Compare_y_on_boundary_2`\endlink:
- Given two points \f$p_1=(x_{p_1},y_{p_1})\f$ and \f$p_2=(x_{p_2},y_{p_2})\f$, such that at least one of them lies on a vertical boundary side, compare the \f$y\f$-coordinates of the points. That is, compare \f$y_{p_1}\f$ and \f$y_{p_2}\f$. If \f$p_1\f$ (resp. \f$p_2\f$) is on the boundary; that is, \f$x_{p_1} \in \{x_{\rm min},x_{\rm max}\}\f$ (resp. \f$x_{p_2} \in \{x_{\rm min},x_{\rm max}\}\f$), then the vertical boundary side containing \f$p_1\f$ (resp. \f$p_2\f$) must be either closed or identified. In other words, this overloaded version is required only for the concepts `AosClosedLeftTraits_2`, `AosClosedRightTraits_2`, and `AosIdentifiedVerticalTraits_2`.
- \link AosVerticalSideTraits_2::Compare_y_near_boundary_2 `Compare_y_near_boundary_2`\endlink:
-
\image html compare_y_near_boundary.png \image latex compare_y_near_boundary.png Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$, and an enumerator \f$i\f$ that specifies either the minimum ends or the maximum ends of the two curves, and thus maps to a parameter value \f$d \in \{0,1\}\f$, compare the \f$y\f$-coordinates of the curves near their respective ends. More precisely, compare the \f$y\f$-coordinates of the vertical projections of a point \f$p\f$ onto \f$c_1\f$ and onto \f$c_2\f$. If the enumerator \f$i\f$ specifies the minimum ends, the curves must approach the left boundary-side. In this case \f$p\f$ is located sufficiently close to the left boundary-side, such that the result is invariant under a translation of \f$p\f$ closer to the left boundary-side. If \f$i\f$ specifies the maximum ends, the curves must approach the right boundary-side. In that case \f$p\f$ is located sufficiently close to the right boundary-side in a similar manner.
- \link AosHorizontalSideTraits_2::Compare_x_on_boundary_2 `Compare_x_on_boundary_2`\endlink:
- This predicate is overloaded with three versions.
We distinguish between open and non-open sides as explained below.
(i) Given a regular point \f$p=(x_p,y_p)\f$, an \f$x\f$-monotone curve
\f$c = (x(t),y(t))\f$, and an enumerator that specifies either the
minimum end or the maximum end of the curve, and thus maps to a
parameter value \f$d \in \{0,1\}\f$, compare the \f$x\f$-coordinate of
\f$p\f$ and the \f$x\f$-coordinate of \f$c\f$ at its respective limit
or end depending on whether it is open or non-open. More precisely, if
\f$c\f$ is open at its \f$d\f$-end, compare the values \f$x_p\f$ and
\f$\lim_{t \rightarrow d} x(t)\f$. A precondition assures that \f$c\f$
has a vertical asymptote at its \f$d\f$-end; that is \f$\lim_{t
\rightarrow d} x(t)\f$ is a real value. If \f$c\f$ is not open,
compare the values \f$x_p\f$ and \f$x(d)\f$.
(iii) Given two points \f$p_1=(x_{p_1},y_{p_1})\f$ and \f$p_2=(x_{p_2},y_{p_2})\f$, such that at least one of them lies on a horizontal boundary side, compare the \f$x\f$-coordinates of the points. That is, compare \f$x_{p_1}\f$ and \f$x_{p_2}\f$. If \f$p_1\f$ (resp. \f$p_2\f$) is on the boundary; that is, \f$y_{p_1} \in \{y_{\rm min},y_{\rm max}\}\f$ (resp. \f$y_{p_2} \in \{y_{\rm min},y_{\rm max}\}\f$), then the boundary side containing \f$p_1\f$ (resp. \f$p_2\f$) must be either closed or identified. In other words, this overloaded version is required only for the concepts `AosClosedBottomTraits_2`, `AosClosedTopTraits_2`, and `AosIdentifiedHorizontalTraits_2`.\image html compare_x_on_boundary.png \image latex compare_x_on_boundary.png (ii) Given two curves \f$c_1 = (x_1(t),y_1(t))\f$ and \f$c_2 = (x_2(t),x_2(t))\f$ and enumerators that specify either the minimum end or the maximum end of each curve, and thus map to parameter values \f$d_1, d_2 \in \{0,1\}\f$, compare the \f$x\f$-coordinates of the curves at their respective limits or ends. More precisely, if \f$c_1\f$ (resp. \f$c_2\f$) is open at its \f$d_1\f$-end (resp. \f$d_2\f$-end), use the value \f$\lim_{t \rightarrow d_1} x_1(t)\f$ (resp. \f$\lim_{t \rightarrow d_2} x_2(t)\f$) for the comparison. A precondition assures that \f$c_1\f$ (resp. \f$c_2\f$) has a vertical asymptote at its \f$d_1\f$-end (resp. \f$d_2\f$-end); that is \f$\lim_{t \rightarrow d_1} x_1(t)\f$ is (resp. \f$\lim_{t \rightarrow d_2} x_2(t)\f$) a real value. If \f$c_1\f$ (resp. \f$c_2\f$) is not open at its \f$d_1\f$-end (resp. \f$d_2\f$-end), use the value \f$x_1(d_1)\f$ (resp. \f$x_2(d_2)\f$) for the comparison. - \link AosHorizontalSideTraits_2::Compare_x_near_boundary_2 `Compare_x_near_boundary_2`\endlink:
-
\image html compare_x_near_boundary.png \image latex compare_x_near_boundary.png Given two \f$x\f$-monotone curves \f$c_1\f$ and \f$c_2\f$ and an enumerator \f$i\f$ that specifies either the minimum ends or the maximum ends of the two curves, and thus map to parameter values \f$d_1, d_2 \in \{0,1\}\f$, respectively, compare the \f$x\f$-coordinate of the curves near their respective limits or ends. A precondition assures that the \f$x\f$-coordinates of the limits or ends of the curves at their respective ends are equal. That is, the predicate `Compare_x_on_boundary_2` applied to \f$c_1\f$, \f$c_2\f$, and \f$i\f$ evaluates to `CGAL::EQUAL`. Formally, compare the \f$x\f$-coordinates of the horizontal projection of a point \f$p\f$ onto \f$c_1\f$ and onto \f$c_2\f$. A precondition assures that \f$c_1\f$ and \f$c_2\f$ have vertical asymptotes at their respective ends. Furthermore, both curves approach the same boundary-side, either the bottom or the top, at their respective ends. If both curves approach the bottom boundary-side, \f$p\f$ is located far to the bottom, such that the result is invariant under a translation of \f$p\f$ farther to the bottom. If both curves approach the top boundary-side, \f$p\f$ is located far to the top in a similar manner.
- \link AosIdentifiedVerticalTraits_2::Is_on_y_identification_2 `Is_on_y_identification_2`\endlink:
- This predicate is overloaded with two versions. (i) Given a point \f$p=(x_p, y_p)\f$, determine whether \f$p\f$ lies in the image of the vertical (and identified) sides of the boundary. More precisely, determine whether \f$x_p \in \{x_{\rm min},x_{\rm max}\}\f$ for all pre-images of \f$p\f$. (ii) Given a curve \f$c\f$, determine whether the entire curve \f$c\f$ lies in the image of the vertical (and identified) sides of the boundary.
- \link AosIdentifiedHorizontalTraits_2::Is_on_x_identification_2 `Is_on_x_identification_2`\endlink:
- This predicate is overloaded with two versions. (i) Given a point \f$p=(x_p, y_p)\f$, determine whether \f$p\f$ lies in the image of the horizontal (and identified) sides of the boundary. More precisely, determine whether \f$y_p \in \{y_{\rm min},y_{\rm max}\}\f$ for all pre-images of \f$p\f$. (ii) Given a curve \f$c\f$, determine whether the entire curve \f$c\f$ lies in the image of the horizontal (and identified) sides of the boundary.
- If \f$\Delta_{c} > 0\f$, the curve is an ellipse. A circle is a special case of an ellipse, where \f$r = s\f$ and \f$t = 0\f$.
- If \f$\Delta_{c} = 0\f$, the curve is a parabola---an unbounded conic curve with a single connected branch. When \f$r = s = t = 0\f$ we have a line, which can be considered as a degenerate parabola.
- If \f$\Delta_{c} < 0\f$, the curve is a hyperbola. That is, it comprises of two disconnected unbounded branches.
- The `RatKernel` template parameter must be substituted by a geometric kernel whose field type is an exact rational type. It is used to define basic geometric entities (e.g., a line segment or a circle) with rational coefficients. Typically we use one of the standard \cgal kernels, instantiated with the number type `NtTraits::Rational` (see below).
- The `AlgKernel` template parameter must be substituted by a geometric kernel whose field type is an exact algebraic type. It is used to define points with algebraic coordinates. Typically, we use one of the standard \cgal kernels, instantiated with the number type `NtTraits::Algebraic` (see below).
- The `NtTraits` template parameter must be substituted by a type that encapsulates all the numeric operations needed for performing geometric computation carried out by the geometric traits class. It defines the `Integer`, `Rational`, and `Algebraic` number-types, and supports several operations on these types, such as conversion between these types, solving quadratic equations, and extracting the real roots of polynomials with integer coefficients. The use of the `CORE_algebraic_number_traits` class, which is included in the arrangement package, is highly recommended. The traits class-template relies on the multi-precision number types implemented in the \core library and performs exact computations on the number types it defines.
- \link Arr_curve_data_traits_2::Curve_2 `Curve_2`\endlink is derived from the basic `BaseTraits::Curve_2` class, extending it by an extra field of type `CurveData`.
- \link Arr_curve_data_traits_2::X_monotone_curve_2 `X_monotone_curve_2`\endlink is derived from the basic `BaseTraits::X_monotone_curve_2` class, extending it by an extra field of type `XMonotoneCurveData`, which must model the concepts CopyConstructible, EqualityComparable, and DefaultConstructible. The latter ensures that every instance of the class template `Arr_curve_data_traits_2` obtained by substituting the `BaseTraits` template parameter with a model of the `AosLandmarkTraits_2` concept models the `AosLandmarkTraits_2` concept as well
- When a curve is subdivided into \f$x\f$-monotone subcurves, its data field of type `CurveData` is converted to an object of type `XMonotoneCurveData` using the `Convert` functor. The object is automatically associated with each of the resulting \f$x\f$-monotone subcurves. Note that by default, the `CurveData` type is identical to the `XMonotoneCurveData` type (and the conversion functor `Convert` is trivially defined). Thus, the data field associated with the original curve is just duplicated and stored with the \f$x\f$-monotone subcurves.
- When an \f$x\f$-monotone curve is split into two (typically, when it intersects another curve), the decorator class automatically copies its data field to both resulting subcurves.
- When two \f$x\f$-monotone curves, \f$c_1\f$ and \f$c_2\f$, intersect, the result may include overlapping sections represented as \f$x\f$-monotone curves. In this case the data fields of \f$c_1\f$ and \f$c_2\f$ are merged into a single `XMonotoneCurveData` object using the `Merge` functor, which is supplied as a parameter to the traits class-template. The resulting object is assigned to the data field of the overlapping subcurves.
- Merging two \f$x\f$-monotone curves is allowed only when (i) the two curves are geometrically mergeable---that is, the base-traits class allows to merge them, and (ii) the two curves store the same data field.