template<class UnionOfBallsBoundaryDS, class ExactNT = CGAL::Gmpq>
class SBL::GT::T_Union_of_balls_boundary_3_builder< UnionOfBallsBoundaryDS, ExactNT >
Functor filling a HDS of the Boundary of an union of balls.
The input is an alpha-complex of a set of balls. The algorithm works in 6 steps:
- 1) Building the vertices: it consists to iterate over the facets of the alpha-complex and to insert one vertex for each SINGULAR facet, and two vertices for each REGULAR facet. Note that a vertex knows its corresponding facet. Furthermore, the associated facet of a vertex is set such that its associated cell is the EXTERIOR one that contains the vertex.
- 2) Building the halfedges: it consists to iterate over the edges of the alpha-complex and inserting pairs of halfedges (one halfedge and its opposite) corresponding to SINGULAR and REGULAR edges. For a SINGULAR edge, the pair of halfedges represents a full circle. For a REGULAR edge, we iterate over the incident cells to this edge: for each interval of EXTERIOR cell in between two facets that are SINGULAR or REGULAR, we insert a pair of halfedges and we link the halfedges to their incident vertex (corresponding to the SINGULAR or REGULAR facets). Note that halfedges know their corresponding edge, and that two opposite halfedges have edges such that the order of their vertices are opposite. Note also that at this step, for each vertex incident to an halfedge, we map the vertex to the opposite halfedge.
- 3) Linking the halfedges: it consists to run an Union-Find algorithm over all halfedges, and then to link all the halfedges in each connected component. To do so, we first link in the Union-Find data structure all halfedges that have a vertex in common (using the map in step 2). Then, for each leader of a connected component, we associate a ball to this leader (note that if the ORIENTATION_TAG of the HDS is set to true, the asscoiated ball is the one on the left of the leader): we recursively link the leader to the halfedge mapped with the incident vertex of the leader that bounds its associated ball, and we repeat this process for the opposite halfedge (with the other ball) of the leader, for the linked halfedge (with the same ball), and for the opposite linked halfedge (with the other ball).
- 4) Building the faces: it consists to iterate over the vertices of the alpha-complex and to insert faces corresponding to the spherical caps of the REGULAR and SINGULAR vertices. For a SINGULAR vertex, a face coresponding to the full ball is inserted. For a REGULAR vertex, an Union-Find algorithms allows to group all consecutive EXTERIOR cells incident to the vertex, defining one face per connected component. Note also that a second Union-Find algorithm is used for grouping the halfedges around the face in CCB: for each CCB, we arbitrarily attach the first one to the face as the reference CCB, and all other ones as holes.
- 5) Linking the faces: it consists to run an Union-Find algorithm for linking all the adjacent faces. The resulting connected components are the connected components of the boundary and are store in the HDS.
- 6) Finding the exterior connected components of faces: it consists to run an Union-Find algorithm over all EXTERIOR cells joined by EXTERIOR facets: then, for each c.c. of faces, we just take one of the incident EXTERIOR of one of the face and check that it is on the same c.c. than an infinite cell.
Note that the algorithm is designed such that it is possible to fill the HDS only with vertices, or with the vertices and the halfedges, or with all the items.
1.9.1