Topological Map

Introduction

Chapters  and are concerned with subdivisions of the plane induced by collections of curves. In this chapter we introduce the topological map. The topological map (CGAL_Topological_map) is a combinatorial structure with no geometric information. Therefore, it can be used as a base class for deriving geometric subdivisions (e.g, 2D planar maps) with different geometries (e.g, on a sphere or torus). The CGAL_Planar_map_2 (Chapter ) is derived from the CGAL_Topological_map on the Euclidean plane. In this section we briefly review the concepts underlying the data structures described in the following sections.

A face, an edge, and a vertex

\paragraphTopological Map, Vertex, Edge, Face: A topological map is a graph which consists of vertices V, edges E, faces F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations. A face of the topological map is defined by the circular sequences (inner and outer) of halfedges along its boundary.

\paragraphIncidence: If a vertex $v$ is an endpoint of an edge $e$, then we say that $v$ and $e$ are incident to one another. Similarly, a face and an edge on its boundary are incident, and a face and a vertex on its boundary are incident (including edges and vertices which are not connected to the outer boundary - see below).

\paragraphHalfedge, Twin, Source, Target: We consider each edge $e$ to be two-sided, representing it by two directed halfedges $\backslash vece$ and $$Twin(\vece) (in other places the twin halfedge is called $Opposite$). A halfedge $\backslash vece$ is an ordered pair $(u,v)$ of its endpoints, and it is directed from $u$, the source, to $v$, the target (there is no need to store both in each halfedge since $$Target(\vece) = Source(Twin(\vece))). We consider each halfedge to lie on the boundary of a single face.

\paragraphConnected Component of the Boundary (CCB): Each connected component of the boundary of a face is defined by a circular list of halfedges.

For a face $f$ of a topological map, we call each connected component of the boundary of $f$ a CCB. In the topological map we have one unbounded face. If $f$ is bounded, we call its outer boundary component the outer-CCB. Any other connected component of the boundary of $f$ is called a hole (or inner CCB).

\paragraphEdges Around Vertex : Every maximal set of halfedges that share the same target can be viewed as a circular list of halfedges ordered around their target vertex. It should be noted that the orientation of the edges around a vertex is opposite that of the halfedges around a face (unlike the convention we adopt for the planar map in Chapter  where the halfedges are oriented counterclockwise around a face and clockwise around a vertex, in the topological map the users are free to choose any other convention).

Source and target vertices, and twin halfedges

\paragraphDoubly Connected Edge List (DCEL): For a topological map, its DCEL representation consists of a connected list of halfedges for every CCB of every face in the subdivision, with additional incidence information that enables us to traverse the subdivision. In particular, for each halfedge the DCEL stores a pointer to its twin halfedge and a next halfedge pointer. In addition, for each halfedge the DCEL stores a pointer to the incident face. See Figure  [ref:fig:DCEL]. For more information about the DCEL representation see  [dBvKOS97] and Chapter  on CGAL_Halfedge_data_structure.

In the following specifications, we implement the subdivision by a DCEL. See Section   for a specification of the requirements for a DCEL in our implementation.

Topological Map

• Class declaration of CGAL_Topological_map<Dcel>.

• Class declaration of Vertex.

• Class declaration of Halfedge.

• Class declaration of Face.

• Class declaration of Ccb_halfedge_circulator.

• Class declaration of Halfedge_around_vertex_circulator.

Requirements for the Topological Map's DCEL class

In addition to the requirements here, the local types Vertex, Halfedge and Face must fulfill the requirements listed in Sections   through  .

• Class declaration of Dcel.

• Class declaration of Dcel::Vertex.

• Class declaration of Dcel::Halfedge.

• Class declaration of Dcel::Face.

Predefined Interface Class

• Class declaration of CGAL_Pm_dcel<V,H,F>.

• Class declaration of CGAL_Tpm_vertex_base.

• Class declaration of CGAL_Tpm_halfedge_base.

• Class declaration of CGAL_Pm_face_base.

Example Programs

//example1.C

#include <CGAL/basic.h>
#include <iostream.h>

#include <CGAL/Topological_map_bases.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Topological_map.h>


typedef CGAL_Pm_dcel<CGAL_Tpm_vertex_base,
                     CGAL_Tpm_halfedge_base,
                     CGAL_Tpm_face_base> Dcel;  

typedef CGAL_Topological_map<Dcel> Tpm;

typedef  Tpm::Halfedge_handle Halfedge_handle;
typedef  Tpm::Vertex_handle   Vertex_handle;
typedef  Tpm::Face_handle     Face_handle;


int main() {

  Tpm t;

  Face_handle uf=t.unbounded_face();

  cout << "inserting edge e1 in face interior ..." ;
  Halfedge_handle e1 = t.insert_in_face_interior(uf);
  CGAL_assertion(t.is_valid());
  cout << "map is valid." << endl;

  cout << "inserting edge e2 from target vertex of e1 ..." ;
  Halfedge_handle e2=t.insert_from_vertex(e1);
  CGAL_assertion(t.is_valid());
  cout <<  "map is valid." << endl;

  cout << "inserting edge e3 between target vertices of e2 and e1->twin() ...";
  Halfedge_handle e3=t.insert_at_vertices(e2,e1->twin());
  CGAL_assertion(t.is_valid());
  cout << "map is valid." << endl;

  return 0;
}

The results look like this:

inserting edge e1 in face interior ...map is valid.
inserting edge e2 from target vertex of e1 ...map is valid.
inserting edge e3 between target vertices of e2 and e1->twin() ...map is valid.

//example2.C
#include <CGAL/basic.h>
#include <iostream.h>

#include <CGAL/Topological_map_bases.h>
#include <CGAL/Pm_default_dcel.h>
#include <CGAL/Topological_map.h>


class Face_with_info : public CGAL_Tpm_face_base {
  int inf;
public:
  Face_with_info() : CGAL_Tpm_face_base(), inf(0) {}

  int info() {return inf;}
  void set_info(int i) {inf=i;}
};

typedef CGAL_Pm_dcel<CGAL_Tpm_vertex_base,
                     CGAL_Tpm_halfedge_base,
                     Face_with_info > Dcel;  

typedef CGAL_Topological_map<Dcel> Tpm;

typedef  Tpm::Halfedge_handle Halfedge_handle;
typedef  Tpm::Vertex_handle   Vertex_handle;
typedef  Tpm::Face_handle     Face_handle;


main() {
  
  Tpm t;

  Face_handle uf=t.unbounded_face();

  cout << "inserting e1 in face interior..." << endl;
  Halfedge_handle e1 = t.insert_in_face_interior(uf);
  CGAL_assertion(t.is_valid());

  cout << "inserting e2 from vertex..." << endl;
  Halfedge_handle e2=t.insert_from_vertex(e1);
  CGAL_assertion(t.is_valid());

  cout << "inserting e3 between vertices of e2 and e1->twin()..." << endl;
  Halfedge_handle e3=t.insert_at_vertices(e2,e1->twin());
  CGAL_assertion(t.is_valid());
  
  cout << endl << "setting info of the new face to 10..." << endl;
  Face_handle nf=e3->face() ;
  nf->set_info(10);

  cout << endl << "unbounded face info = " << uf->info() << endl;
  cout << "new face info = " << nf->info() << endl;

  return 0;
}

The results look like this:

inserting e1 in face interior...
inserting e2 from vertex...
inserting e3 between vertices of e2 and e1->twin()...

setting info of the new face to 10...

unbounded face info = 0
new face info = 10