This page describes the Algorithmische Geometrie Bonn C++-implementation of a quad-edge data structure. I developed this implementation to be able to demonstrate two algorithms for the computation of Voronoi diagrams and Delaunay triangulations. To download the QEDS, please download the Voronoi diagram package, in which the QEDS is included. Note: the AGB-QEDS implementation is still in its first Beta stage. There are no known bugs at this point, but I find that I am still making changes to the interface as I am working on the documentation of the QEDS itself and of the Voronoi diagram code that uses it.

A QEDS stores a connected, undirected planar graph and its dual. It was originally developed by Guibas and Stolfi. For each edge of the graph and for each each of the dual there are essentially two half-edges: one in each direction. Thus, there are four half-edges per edge. These four half-edges are always stored together in one block. This block stores, for each half-edge, a pointer to the half-edge that succeeds it in the counterclockwise order of half-edges with the same origin. All access to the data structure is through pointers to half-edges. A vertex can be accessed through a half-edge that has it as its origin.

The AGB-QEDS implementation allows us to store, for each half-edge, a pointer to an object that represents its origin. For this reason, the half-edge pointers are of a type HalfEdge<V,F>, where V is the type of the vertex objects and F is the type of the face objects (that is, vertices in the dual). Below I describe and illustrate the public operations on HalfEdge<V,F> objects that allow us to create, maintain and use a QEDS and keep it in a consistent state. Some of the figures show dashed edges: these are edges of the dual. The half-edge to which a pointer is returned is denoted by ret. All operations run in constant time, unless indicated otherwise.

HalfEdge<V,F>::createEdge(v₁, v₂, F) creates a graph that consists of two vertices connected by an edge. The arguments are optional and specify pointers to objects that represent the origin and the destination vertex and the surrounding face of the edge that is returned. If the arguments are omitted, NULL is used.

HalfEdge<V,F>::createLoop(F₁, v, F₂) creates a graph that consists of a single loop. The arguments are optional and specify pointers to objects that represent the inner face, the vertex, and the outer face of the loop. If the arguments are omitted, NULL is used. The half-edge that is returned has the inner face to its left.

Vertices can be inserted with this→insertVertex(v) and this→insertStar(v). The vertex object pointer v can be omitted (in that case, NULL is used). In the case of insertStar, the newly created faces all get the face object pointer from the face that ceases to exist, and the running time is proportional to the number of new edges that are created. Careful with insertVertex: if any pointer to the half-edge in the opposite direction exists outside the data structure itself when this→insertVertex(v) is called, then afterwards, the origin of that opposite half-edge will be the new vertex.

this→flip() flips the common edge of two triangular faces. These faces should have the same face object pointer, which will also be the face object pointer of the new triangles:

HalfEdge<V,F>::joinOrigins(e,f), …insertGraph…, …splitOrigin…, …splitGraph…, …splitFace…, …expandOrigin…, and …cutIntoFace… have the effects shown in the figure below. The first four operations actually have the same implementation, they only differ in their preconditions, and thus, in their postconditions. Using the correct version for the intended effect makes it possible to verify (some of) these preconditions, which may help in debugging any code that uses these operations. joinOrigins, splitOrigin, and splitFace are to be used when, on the upper right-hand side, e and f have the same face of the same graph to the left, whereas insertGraph and splitGraph are to be used when, on the right-hand side, e and f are not in the same connected component of the same graph. joinOrigins and insertGraph require that the origins of e and f have the same vertex object pointer. splitOrigin and splitGraph require that e and f have the same face object pointer for the face to the left. cutIntoFace optionally takes a third argument v, the vertex object pointer for the newly created vertex.

this→deleteSubgraph(e) deletes the entire subgraph that is enclosed by the sequence of edges that is obtained by starting from e and proceeding to the counterclockwise successor on the face to the left, up to but not including *this. Note that only the halfedges of the subgraph are removed; vertex and face objects will not be deleted automatically and may become inaccessible when the subgraph is deleted. The running time is linear in the size of the subgraph that is deleted.

this→zipUp() collapses *this and its predecessor on the face to the left into one edge, and repeats the process with the successor on the face to the left, until the entire face is gone. Prior to the zipUp operation, the vertices that will be merged must have the same vertex object pointer, and the number of edges on the face must be even. The running time is linear in the size of the face that is removed.

HalfEdge<V,F>::deleteGraph(e) deletes the entire graph that contains the half-edge e. Only the halfedges of the graph are removed; vertex and face objects will not be deleted automatically and may become inaccessible when the graph is deleted. The running time is linear in the number of edges of the graph.

this→labelOrigin(v) sets the vertex object pointer for the origin of *this to v. The running time is linear in the degree of the origin of *this, as the pointer needs to be set for all half-edges with the same origin.

this→labelLeftFace(F) sets the face object pointer for the face to the left of *this to F. The running time is linear in the size of the boundary of the face, as the pointer needs to be set for all half-edges that have this face to the left.

The neighbourhood of a half-edge can be accessed through several methods that can be applied to HalfEdge objects. To remember the names of these operations, note: s = successor, p = predecessor, c = clockwise, cc = counterclockwise, left = left face, right = right face, ltor = left-to-right, rtol = right-to-left:

In addition there are the following operations:

tosccorgn(e) changes the HalfEdge pointer e into a pointer to the successor around the origin. Thus, we can implement a loop that visits all edges with a common origin as follows: HalfEdge<V,F> s = e ; do process e ; while (tosccorgn(e) != s);.

this→hasSameOrigin(e) tests whether *this and e have the same origin, not by looking at pointers to vertex objects, but by testing whether one edge can be reached from the other by applying the tosccorgn operator zero or more times. The running time of this function is linear in the minimum of the degrees of the origins of *this and e.

this→hasSameLeftFace(e) tests whether *this and e have the same face to the left, not by looking at pointers to face objects, but by testing whether the left-to-right dual of one edge can be reached from the left-to-right dual of the other by applying the tosccorgn operator zero or more times. The running time of this function is linear in the minimum of the boundary complexities of the faces to the left of *this and e.

this→nrEdgesOnOrigin() returns the degree of the origin of *this, that is, the number of times one would have to apply the tosccorgn operator to get back to the original half-edge. The running time of this function is linear in the degree of the origin.

this→nrEdgesOnLeftFace() returns the boundary complexit of the face to the let of *this, that is, the number of times one would have to apply sccleft() to get back to the original half-edge. The running time of this function is linear in that number.

this→getEdges() returns a stl vector of half-edge pointers, one half-edge (with arbitrary direction) for each edge of the graph. The running time is linear in the number of edges of the graph.

this→getVertices() returns a stl vector of half-edge pointers, one outgoing half-edge for each vertex of the graph. The running time is linear in the number of edges of the graph.