<jupyter_start><jupyter_text>The Half-Edge Data Structure CS 480 Computational Geometry Dr. <NAME>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)$ time.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 `Polygon` objects, each of which represented one of the triangles. This is not terribly convenient. For instance, suppose you are writing the AI for a computer game and the game map is represented as a triangluation. You want to do path planning for your NPCs, so given a current location of an NPC and its desired location, you'd like to get a path through the map that will move the NPC from the starting position to the ending position. As a first pass, you'd just like the sequence of map triangles the NPC will traverse. If your map is stored as a "triangle soup" (a flat list of triangles) then just finding the three neighboring triangles to any given triangle requires a linear-time search. This will not lead to efficient algorithms. What is needed is a spacial data structure that can elegantly store subdivisions of the plane into polygonal regions and answer lots of queries efficiently. Queries like, what are the vertices / edges of some given face? What are the edges incident to a given vertex? What are the faces incident to a given edge? Whast are the faces incident along the edges of some other face? Etc. Remarkably a powerful data structure exists that answers these queries and more _as efficiently as possible_. The data structure is actually quite simple, though it is a little bit fiddly to get right--because it is a generalization of doubly-linked lists. The data structure is often called the _half-edge datastructure_ (and is also known as a _doubly-connected edge list_ or _DCEL_).In this lab we will develop a half-edge data structure for storing subdivisions of some polygon into polygonal regions without holes. Note though that with slight modifications the data structure developed here can be extended to store more generally _any_ planar striaght-line graph--_PSLG_--a non-crossing embedding of a planar graph in the plane with edges represented as striaght line segments. It can also be used to store piecewise-linear surfaces in $\mathbb{R}^3$ like polyhedra so long as they are manifolds--meaning that each edge is incident to at most two faces. The basic ideaConsider the following subdivision of a large outer polygon into smaller polygons: ![A planar subdivision.](img/planarsubdiv.png)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_ _h1_ and _h2_. The split is not what you'd think. We're __not__ splitting the edge in half at its midpoint to get two edges that are half as long. Instead, the split is like Robin Hood's arrow splitting an already shot arrow straight through its core. We are splitting the edge along its entire length into a left-side half-edge and a right-side half-edge. This allows us to maintain a few useful invariants: 1. A half-edge is incident to only one face, unlike an edge which is incident to two. 2. Each half-edge runs counter-clockwise along the face it is incident to. The two half-edges that together make up the left-side and right-side of an edge of our planar subdivision are called _twins_. A face can now 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 (note how the orange edges have been split into red half-edges):![img/dcel1.png](img/dcel1.png)Side note: in some of the more topological literature _half-edges_ are referred to as _darts_.  A few more detailsSo much for the basic idea, let's dive into a few more details. First, it's convenient to store three different types of objects: vertices, half-edges, and faces. We may even add an edge structure if we need to maintain data on a per-edge basis--in this case the edge structure is just a container for data and both its incident half-edges maintain a reference to it. Each half-edge stores the following: 1. A reference to its _originating vertex_--the first vertex of its edge in the ccw ordering of the half-edge's face. 2. A reference to its _incident face_. 3. References to its _next_ and _previous_ half-edges in ccw order along the incident face. 4. A reference to its _twin_ half-edge.Notice that the half-edge stores a reference to its origin vertex, but not its destination vertex. How can we recover the destination? Suppose `he` is a reference to a half-edge and `he.origin` is the origin vertex. Then the destination vertex is simply `he.twin.origin`. __Question:__ What is another way we can get the destination of a given half-edge `he`? Each `Face` object simply stores a pointer to _any one of its incident half-edges (arbitrarily)_. This has the role of the _firstVertex_ reference we used in the `Polygon` structure for the convex-hull lab. If you have a `Face` object, you can start a loop over all its incident half-edges by starting from `.incidentEdge` and following `.next` references (to obtain the half-edges in ccw order) or `.prev` references (to obtain the half-edges in cw order) . __Question:__ How can you list all the vertex coordinates incident to a face in ccw order? Similar to a `Face`, each `Vertex` simply stores a pointer to _one of its out-going half-edges (arbitrarily)_. This gives us linear-time access to all of the edges incident to a vertex. __Question:__ How can we loop over all of the half-edges outgoing from a vertex? HINT: Think about starting from the vertex's `.outgoingHalfEdge` refference and following `twin` and `next` pointers to pick up the others. Here's a more complete picture oif the previous half-edge structure: ![img/dcel2.png](img/dcel2.png) A Combinatorial StructureNotice that nothing in the above discussion is geometric. In fact, the half-edge structure is a combinatorial structure that maintains how the faces, edges (half-edges), and vertices of a manifold are combined--but not _where_ they are in some particular geometry. In order to add geometric information, we need to store a `.pos` attribute at each vertex. UML DiagramTODO The LabA skeleton of the `DCEL`, `Vertex`, `HalfEdge`, and `Face` data structures appears int the code block below. Note that the constructors for `Vertex`, `HalfEdge`, and `Face` all take their parent `DCEL` object as a parameter. This way, each element is able to automatically add itself to the `DCEL`'s `.verts`, `.halfEdges`, and `.faces` lists so that you don't have to do the book-keeping directly. Have a look at the code and get comfortable with it.<jupyter_code>class DCEL:
    """
    The basic DCEL container. 
    
    Attributes:
        verts: List[Vertex] - The list of vertices. 
        halfEdges: List[HalfEdge] - The list of half-edges. 
        faces: List[Face] - The list of faces. 
        outerFace: Face - The outerFace (None if there isn't one.)
    """
    def __init__(self):
        self.verts = []
        self.halfEdges = []
        self.faces = []
        self.outerFace = None
    
    def splitFace(he1, he2):
        """
        Splits the face incident to he1 and he2 by adding an edge
        between the origins of he1 and he2. If he1 and he2 are not
        incident to the same face, or he1 is the .next or .prev of
        he2, then the operation is illegal and no change should
        occur to the DCEL. 
        
        Parameters:
            he1: HalfEdge
            he2: HalfEdge
            
        Returns:
            True if the oepration succeeds, False if there is an error.
        """
        # TODO
        # 0. Check whether the call is legal and return False if not.
        # 1. Create a new face for the second half of the split. 
        # 2. Create new half-edges for the splitting edge. 
        # 3. Insert your new half-edges into the cyclic lists. 
        # 4. Make sure that all the half-edges point to the right face. 
        # 5. Make sure that each face correctly points to an incident half edge. 
        pass
    
class Vertex:
    """
    The basic Vertex object. 
    
    Attributes:
        dcel: DCEL - The parent DCEL. 
        outgoingHalfEdge: HalfEdge - Any one half-edge with this vertex as its origin.
        
    """
    def __init__(self, dcel, outgoingHalfEdge=None, pos=None):
        self.dcel = dcel
        self.dcel.verts.append(self)
        self.outgoingHalfEdge = outgoingHalfEdge
        self.pos = pos

class Face:
    def __init__(self, dcel, incidentHalfEdge=None):
        self.dcel = dcel
        self.dcel.faces.append(self)
        self.incidentHalfEdge = incidentHalfEdge
    
    def incidentHalfEdges(self):
        # TODO
        return []
    
    def incidentVertices(self):
        # TODO
        return []

class HalfEdge:
    def __init__(self, 
                 dcel, 
                 origin=None, 
                 face=None, 
                 prev=None, 
                 next=None, 
                 twin=None):
        
        self.dcel   = dcel
        self.dcel.halfEdges.append(self)
        
        self.origin = origin
        self.face   = face
        self.prev   = prev
        self.next   = next
        self.twin   = twin
    
    def makeNext(self, he):
        self.next = he
        he.prev = self
    
    def makeTwin(self, he):
        self.twin = he
        he.twin = self
    
    @property # The @property annotation let's you "run" this as
              # he.destination instead of he.destination()
    def destination(self):
        return self.twin.origin
    
    def splitInHalf(self):
        # TODO
        # 1. Create a vertex for the mid-point
        # 2. Create new half-edges
        # 3. Set next/prev/twin/face pointers correctly
        pass<jupyter_output><empty_output><jupyter_text>TasksYour tasks are to implement the following methods:* `Face.incidentHalfEdges() -> List[HalfEdge]`. Returns a list of the incident half-edges in order. * `Face.incidentVertices() -> List[Vertex]`. Returns a list of the incident vertices in order.* `DCEL.splitFace(he1, he2) -> bool`. Splits the face incident to the half-edges `he1` and `he2` by adding an edge (i.e. two half-edges that are twins) between the origins of `he1` and `he2`. Your code should check that the two are incident to the same face and are also not coincident along the face. If both checks pass, then you should split the face and return `True`. Otherwise, you shouldn't modify the `DCEL` and return `False`. * `HalfEdge.splitInHalf()`. This splits the half-edge and its twin by introducing a vertex at its mid-point and creating a few additional half-edges. Note that if `p` and `q` are `PointE2` objects, then the midpoint is given by `((p.x + q.x) / 2, (p.y + q.y) / 2)`. Once you have implemented the methods above, test your split face code by reproducing the following drawing using only calls to `splitFace` and `splitInHalf` methods. Add your code for this after the comment ` YOUR CODE HERE`.<jupyter_code>from koebe.geometries.euclidean2 import PointE2, PolygonE2

coords = [PointE2(-250, -150), PointE2(0, -150), PointE2( 250, -150), 
          PointE2( 250,  150), PointE2(0,  150), PointE2(-250,  150)]

dcel = DCEL()

# Create vertices
for p in coords: Vertex(dcel, pos=p)

# Create the outerFace: 
dcel.outerFace = Face(dcel)

# Create the inner face: 
f = Face(dcel)

# Create six half-edges for the inner face
innerHEs = [HalfEdge(dcel, v, f) for v in dcel.verts]
twinHEs = [HalfEdge(dcel, v, dcel.outerFace) for v in dcel.verts[1:] + [dcel.verts[0]]]

for i in range(len(innerHEs)):
    innerHEs[i-1].makeNext(innerHEs[i])
    twinHEs[i].makeNext(twinHEs[i-1])
    innerHEs[i].makeTwin(twinHEs[i])

f.incidentHalfEdge = innerHEs[0]
dcel.outerFace.incidentHalfEde = twinHEs[0]

# YOUR CODE HERE

from koebe.graphics.euclidean2viewer import E2Viewer, makeStyle

viewer = E2Viewer(600, 600)
viewer.addAll([SegmentE2(he.origin.pos, he.destination.pos) for he in dcel.halfEdges])
viewer.addAll([v.pos for v in dcel.verts])
facePolys = [PolygonE2(vertices=[v.pos for v in face.incidentVertices()]) for face in dcel.faces if face != dcel.outerFace]
for poly in facePolys: viewer.add(facePolys, makeStyle(fill="#f00"))
viewer.show()<jupyter_output><empty_output>