Planar Straight Line Graphs:Winged-Edge

Winged-Edge

The winged-edge data structure was introduced by Baum gart [1] and it predates the half edge and quad edge data structures. There are three kinds of records: vertex records, edge records, and face records. Each vertex record keeps a reference to one incident edge of the vertex. Each face record keeps a reference to one boundary edge of the face. Each edge e is stored as an oriented edge with the following references (see Figure 17.8):

• The origin endpoint e.org and the destination endpoint e.dest of e. The convention is that e is directed from e.org to e.dest.

• The faces e.left and e.right on the left and right of e, respectively.

• The two edges e.lcw and e.lccw adjacent to e that bound the face e.left. The edge e.lcw is incident to e.org and the edge e.lccw is incident to e.dest. Note that e.lcw (resp. e.lccw ) succeeds e if the boundary of e.left is traversed in the clockwise (resp. anti-clockwise) direction from e.

• The two edges e.rcw and e.rccw adjacent to e that bound the face e.right. The edge e.rcw is incident to e.dest and the edge e.rccw is incident to e.org. Note that e.rcw (resp. e.rccw ) succeeds e if the boundary of e.right is traversed in the clockwise (resp. anti-clockwise) direction from e.

The information in each edge record can be retrieved in constant time. Given a vertex v, an edge e, and a face f , we can thus answer in constant time whether v is incident on e and e is incident on f . Given a vertex v, we can traverse the edges incident to v in clockwise order as follows. We output the edge e kept at the vertex record for v. We perform e := e.rccw if v = e.org and e := e.lccw otherwise. Then we output e and repeat the above. Given a face f , we can traverse its boundary edges in clockwise order as follows. We output the edge e kept at the face record for f . We perform e := e.lcw if f = e.left and e := e.rcw otherwise.

Then we output e and repeat the above.

Note that an edge reference does not carry information about the orientation of the edge. Also, the orientations of the boundary edges of a face need not be consistent with either the clockwise or anti-clockwise traversal. Thus, the manipulation of the data structure is often complicated by case distinctions. We illustrate this with the insertion of an edge e. Assume that e.org = u, e.dest = v, and both u and v already exist. The input also specifies two edges e1 and e2 incident to u and v, respectively. The new edge e is supposed to immediately succeed e1 (resp. e2) in the anti-clockwise ordering of edges around u (resp.

v). The insertion routine works as follows.

1. If u = vinf and it is isolated, we need to store the reference to e in the vertex record for u. We update the vertex record for v similarly.

2. Let e3 be the incident edge of u following e1 such that e is to be inserted between e1 and e3. Note that e3 succeeds e1 in anti-clockwise order. We insert e between e1 and e3 as follows.

Notice the inconvenient case distinctions needed in steps 2, 3, and 4. The half edge data structure is designed to keep both orientations of the edges and link them properly. This eliminates most of these case distinctions as well as simplifies the storage scheme.