Planar Straight Line Graphs:Quad edge.

Quad edge

The quad edge data structure was introduced by Guibas and Stolfi [8]. It represents the planar subdivision and its dual simultaneously. The dual S∗ of a PSLG S is constructed as follows. For each face of S, put a dual vertex inside the face. For each edge of S bordering the faces f and f l, put a dual edge connecting the dual vertices of f and f l. The dual of a vertex v in S is a face and this face is bounded by the dual of the incident edges of v.

Figure 17.14 shows an example.

The dual may have loops and two vertices may be connected by more than one edge, so the dual may not be a PSLG. Nevertheless, the quad edge data structure is expressive enough to represent the dual. In fact, it is powerful enough to represent subdivisions of both orient able and non-orient able surfaces. We describe  a simplified version sufficient for our purposes.

Each edge e in the PSLG is represented by four quad edges e[i], where i ∈ {0, 1, 2, 3}. The quad edges e[0] and e[2] are the two oriented versions of e. The quad edges e[1] and e[3] are the two oriented versions of the dual of e. These four quad edges are best viewed as a cross such as e[i + 1] is obtained by rotating e[i] for π/2 in the anti-clockwise direction. This is illustrated in Figure 17.15. The quad edge e[i] has a next field referencing the quad edge that has the same origin as e[i] and follows e[i] in anti-clockwise order. In effect, the next fields form a circular linked list of quad edges with a common origin. This is called an edge ring.

The quad edge data structure is entirely edge based and there are no explicit vertex and face records.

The following two basic operations make edge and splice are central to the operations on PSLGs supported by the quad edge data structure. Our presentation is slightly different from that in the original paper [8].

• make edge(u, v): Return an edge e connecting the points u and v. The quad edges e[i] where 0 ≤ i ≤ 3 are initialized such that they represent a new PSLG with e as the only edge. Also, e[0] is the quad edge directed from u to v. If u and v are omitted, it means that the actual coordinates of the endpoints of are unimportant.

• splice(a, i, b, j): Given two quad edges a[i] and b[j], let (c, k) = rot(a[i].next ) and (d, l) = rot(b[j].next ), splice swaps the contents of a[i].next and b[j].next and the contents of c[k].next and d[l].next. The effects on the edge rings of the origins of a[i] and b[j] and the edge rings of the origins of c[k] and d[l] are:

– If the two rings are different, they are merged into one (see Figure 17.16(a)).

– If the two rings are the same, it will be split into two separate rings (see Figure 17.16(b)).

Notice that make edge and splice are similar to the operations make half edges and half splice introduced for the half edge data structure in the previous section. As mentioned before, they inspire the definitions of make half edges and half splice. Due to this similarity, one can easily adapt the edge insertion, edge deletion, vertex split, and edge contraction algorithms in the previous section for the quad edge data structure.