Planar Straight Line Graphs:Half edge

Half edge

In the half edge data structure, for each edge in the PSLG, there are two symmetric edge records for the two possible orientations of the edge [15]. This solves the orientation problem in the winged-edge data structure. The half edge data structure is also known as the doubly connected edge list [3]. We remark that the name doubly connected edge list was first used to denote the variant of the winged-edge data structure in which the lccw and rccw fields are omitted [12, 13].

There are three kinds of records: vertex records, halfedge records, and face records. Let e be a halfedge. The following information is kept at the record for e (see Figure 17.9).

• The reference e.sym to the symmetric version of e.

• The origin endpoint e.org of e. We do not need to store the destination endpoint of e since it can be accessed as e.sym.org. The convention is that e is directed from e.org to e.sym.org.

• The face e.left on the left of e.

• The next edge e.succ and the previous edge e.pred in the anti-clockwise traversal around the face e.left.

For each vertex v, its record keeps a reference to one halfedge v.edge such that v = v.edge.org . For each face f , its record keeps a reference to one halfedge f.edge such that f = f.edge.left .

We introduce two basic operations make halfedges and half splice which will be needed for implementing the operations on PSLGs. These two operations are motivated by the operations make edge and splice introduced by Guibas and Stolfi [8] for the quadedge data structure. We can also do without make halfedges and half splice, but they make things simpler.

• make halfedges(u, v): Return two halfedges e and e.sym connecting the points u and v. The halfedges e and e.sym are initialized such that they represent a new PSLG with e and e.sym as the only halfedges. That is, e.succ = e.sym = e.pred and e.sym.succ = e = e.sym.pred . Also, e is the halfedge directed from u to v. If u and v are omitted, it means that the actual coordinates of e.org and e.sym.org are unimportant.

• half splice(e1, e2): Given two halfedges e1 and e2, half splice swaps the contents of e1.pred and e2.pred and the contents of e1.pred .succ and e2.pred .succ.

The effects are:

– Let v = e2.org . If e1.org /= v, the incident halfedges of e1.org and e2.org are merged into one circular list (see Figure 17.10(a)). The vertex v is now

The behavior of half splice is somewhat complex even in the following special cases. If e is an isolated half edge, half splice(e1, e) deletes the vertex record for e.org and makes e a half edge incident to e1.org following e1 in anti-clockwise order. If e1 = e.sym. succ, half splice(e1, e) detaches e from the vertex e1.org and creates a new vertex record for e.org. If e1 = e, half splice(e, e) has no effect at all.

Access functions

The information in each half edge record can be retrieved in constant time. Given a vertex v, a half edge e, and a face f , we can thus answer the following adjacency queries:

1: Is v incident on e? This is done by checking if v = e.org or e.sym.org .

2: Is e incident on f ? This is done by checking if f = e.left .

3: List the halfedges with origin v in clockwise order. Let e = v.edge. Output e, perform e := e.sym.succ, and then repeat until we return to v.edge.

4: List the boundary halfedges of f in anti-clockwise order. Let e = f.edge. Output e, perform e := e.succ, and then repeat until we return to f.edge.

Other adjacency queries (e.g., listing the boundary vertices of a face) can be answered similarly.

Edge insertion and deletion

The edge insertion routine takes two vertices u and v and two half edges e1 and e2. If u is a new vertex, e1 is ignored; otherwise, we assume that e1.org = u. Similarly, if v is a new vertex, e2 is ignored; otherwise, we assume that e2.org = v. The general case is that an edge connecting u and v is inserted between e1 and e1.pred .sym and between e2 and e2.pred .sym . The two new halfedges e and e.sym are returned with the convention that e is directed from u to v.

 

Algorithm insert(u, v, e1, e2)

The following deletion algorithm takes the two half edges e and e.sym corresponding to the edge to be deleted. If the edge to be deleted borders two adjacent faces, they have to be merged after the deletion.

Vertex split and edge contraction

Recall that each face is assumed to be a simple polygon for the vertex split and edge contraction operations. The vertex split routine takes two points (p, q) and (x, y) and four half edges e1, e2, e3, and e4 in anti-clockwise order around the common origin v. It is required that either e1 = e2 or e1.pred = e2.sym and either e3 = e4 or e3.pred = e4.sym. The routine splits v into an edge e connecting the points (p, q) and (x, y). Also, e borders the faces bounded by e1 and e2 and by e3 and e4. Note that if e1 = e2, we create a new face bounded by e1, e2, and e. Similarly, a new face is created if e3 = e4. The following is the vertex split algorithm.

The following algorithm contracts an edge to a point (x, y), assuming that the edge contractibility has been checked.