ApolloniusGraphDataStructure_2
Definition
The concept ApolloniusGraphDataStructure_2 refines the concept
TriangulationDataStructure_2. In addition
it provides two methods for the insertion and removal of a degree 2
vertex in the data structure. The insertion method adds a new vertex
to the specified edge, thus creating two new edges. Moreover, it
creates two new faces that have the two newly created edges in
common (see figure below). The removal method performs the reverse
operation.
Figure 36.4: Insertion and removal of degree 2 vertices. Left to right:
The edge (f,i) is replaced by two edges by means of inserting a
vertex v on the edge. The faces and are
created. Right to left: the faces and are
destroyed. The vertex v is deleted and its two adjacent edges
are merged.
We only describe the additional requirements with respect to the
TriangulationDataStructure_2 concept.
Refines
TriangulationDataStructure_2
Insertion
|
Vertex_handle
|
agds.insert_degree_2 ( Face_handle f, int i)
|
| |
Inserts
a degree two vertex and two faces adjacent to it that have two common
edges. The edge defined by the face handle f and the integer
i is duplicated. It returns a handle to the vertex created.
|
Removal
|
void
|
agds.remove_degree_2 ( Vertex_handle v)
|
| |
Removes a degree 2
vertex and the two faces adjacent to it. The two edges of the star of
v that are not incident to it are collapsed.
| Precondition: | The degree of v must be equal to 2. |
|
Has Models
CGAL::Triangulation_data_structure_2<Vb,Fb>
See Also
TriangulationDataStructure_2
ApolloniusGraphVertexBase_2
TriangulationFaceBase_2
