Half-Edge Data Structure

We’ve seen in this class that storing polygons as doubly-linked lists of vertices is convenient for supporting many of the operations needed for dealing with polygons in algorithms. For example, when combining two convex polygons across tangents into a larger convex polygon (in the divide-and-conquer convex hull algorithm), the required operations were very fast–once the tangents where identified, the actual combination operation runs in $O(1)$.

Recall, however, our early triangulation of polygons lab. In that lab we triangulated a polygon using a naive algorithm for finding a maximal non-crossing set of diagonals. We returned a list of diagonals as an ArrayList<Diagonal>. This is not terribly convenient. For instance, suppose you wanted to locate which triangle contained some point on the polygon’s interior. This is a common operation–the polygon could represent some region of a game map in a computer game, and the artificial intelligence class for an NPC needs to know where the character its controlling is on the map. A flat list of diagonals does not give us a convenient way of finding that information, nor tracking the movement of the NPC as it moves among different regions of the polygon. We really need some sort of spacial data structure that can elegantly store subdivisions of the plane into polygonal regions and answer lots of different queries efficiently. Today we will learn one such data structure that is relatively simple, but very powerful–the half-edge data structure. (Note that sometimes this data structure is called the doubly-connected edge list, or DCEL.)

We will look at storing a subdivision of a polygon into regions using the half-edge data structure, but in fact with slight modifications it can be used to store (more generally) any planar straight-line graph (PSLG) (a non-crossing embedding of a planar graph in the plane with edges represented as straight-line segments). (For the mathematically inclined–it can also be used to store piecewise-linear surfaces in $R^3$ so long as they are manifolds–meaning that each edge is incident to at most two faces; an example of this is any 3D folded state of a origami crease pattern).

The basic idea

Consider the following subdivision of a large outer polygon into smaller polygons:

The subdivision above has 8 vertices, 12 edges, and 6 faces (note that we are counting the outer face here, and this is important, because it will allow us to keep special cases out of our data structure).

Suppose we want a data structure for representing the vertices, edges, and faces of our subdivision. We could try to use a doubly-linked list for representing each polygon, like we did before, but there’s a problem: given some edge $e$, where should its next pointer point? What’s the problem exactly? The problem is that each edge is incident to two faces, not one, and so there are really two “next” edges, one in each of $e$’s incident faces. The problem is made even worse by the following observation, the counter-clockwise orientation of the two faces incident $e$ runs in opposite directions along $e$ in the two incident faces. It seems there is just no good way to store an edge in a doubly-linked list as we did before.

Or is there?

Enter the half-edge data structure. The basic idea is to split each edge $e$ into two half-edges $h_1$ and $h_2$, one for each face incident to $e$. In fact, we’ll maintain the following invariant: each half-edge runs counter-clockwise along the face it is incident to. The two half-edges that together make up an edge of our planar subdivision are called twins. Now, unlike edges in a planar subdivision, half-edges are incident to one and only one face. A face can thus be represented by a doubly-linked list of half-edges, just as we did for representing polygons. Two different faces that share a common edge will simply have two half-edges (that represent the common edge) that are twins of each other. Here’s a drawing of the half edge data structure for the planar subdivision drawing above:

Pretty cool, non?

A few more details

So much for the basic idea, let’s dive in to a few more details. First, its convenient to store three different types of objects: vertices, faces, and half-edges.

Each HalfEdge should store the following: 1. a reference to its originating vertex–its first vertex in the ccw ordering along its face; 2. a reference to its incident face; 3. references to the next and previous half-edges along its incident face; 4. a reference to its twin half-edge; and 5. a reference to its incident face.

Notice that the half-edge stores a reference to its origin vertex, but not its destination. How can we recover the destination? Suppose he is a reference to a half-edge. Then he.twin.origin is its destination (why?).

Question: What is another way we can get at the destination of a half-edge?

Each Face simply stores a pointer to one of its incident half-edges (arbitrarily). This acts sort of like the firstVertex reference we used in the convex-hull lab. If you have a Face object, you can start a loop over all incident half-edges by starting from its incidentEdge reference and following next (or prev) pointers until you get all the way around back to where you started.

Question: How can you list all the vertex coordinates incident to a Face in counter-clockwise order?

Each Vertex simply stores a pointer to one of its out-going half-edges (arbitrarily). This gives you linear time access to all of the edges incident to the vertex.

Question: How can you loop over all of the half-edges outgoing from a vertex? HINT: think about starting from a vertex’s outgoingEdge reference, and following twin and next pointers to pick all of the out-going half-edges up.

Here’s a more complete picture of the previous half-edge structure:

The Lab

Download the starter code here. Open CS480DCEL01.pde file and have a look at the DCEL tab. Notice that the DCEL has a nested class structure–it contains within it definitions for Vertex, HalfEdge, and Face structures. This nesting requires an object of type DCEL to create a Vertex, HalfEdge, or Face. For instance, if you want to create a new Vertex for a DCEL named myDcel you would do:

DCEL.Vertex v = myDcel.new DCEL.Vertex(new Point2d(0, 0));

This object construction may be a little bit more complicated than you have seen before, so let’s unpack it a litte. Since the Vertex class is nested within the DCEL class, from the outside the type Vertex is really DCEL.Vertex. So DCEL.Vertex v declares a new Vertex named v. Now, because the Vertex class is nested, you can only create a new Vertex within the context of an existing DCEL object. This is why we call myDcel.new rather than new to create the object. Now, within the vertex class we can use this to refer to the Vertex object itself, and DCEL.this to refer to the enclosing DCEL object, which in this case is myDcel. We use this to have the constructor for Vertex also update the DCEL container structure without having to take a DCEL as a parameter. Have a look at the DCEL.Vertex constructor. Notice the line:

DCEL.this.vertices.add(this);

This line adds the newly created vertex to the list of vertices stored in the DCEL object itself. Note that Java will actually find the binding implicitly, so we could have written:

vertices.add(this);

but I wanted to make it clear that the vertices object is the one stored in the enclosing DCEL structure.

Have a look over the code and get comfortable with it. Ask any clarification questions at this point, as this will benefit everyone in the class.

Tasks

Your tasks are to implement the following functions:

• DCEL.getCycleFrom(HalfEdge e). Returns an ArrayList containing all the HalfEdges in the face incident to $e$ in counter-clockwise order starting from $e$.
• DCEL.splitFace(HalfEdge e1, HalfEdge e2). Splits the edge incident to e1 and e2 by adding an edge (i.e. two half-edges that are twins) between the origins of e1 and e2. Your code should first check that e1 and e2 are incident to the same face and are also not coincident in the counter-clockwise order of half-edges. If both checks pass, then you should split the face. Note that this requires several steps outlined in the comments.
• DCEL.HalfEdge.splitInHalf(). This splits the edge represented by this half-edge into two at the mid-point of the edge. For your convenience there is a midPoint method in the Point2d tab that can be used to obtain the mid-point between two Point2d objects.

Once you have implemented the methods above, test your split face code by reproducing the following drawing using only the splitFace and splitInHalf methods. Add the code for this after the comment // Test your split face code: in the CS480DCEL01 tab.

Turning it in

Turn it in on Canvas by Monday 11:55pm.