Planar Subdivisions and the Doubly Connected Edge List

Part 6 turned a set of segments into an ordered stream of intersection events. Once those intersections are split into vertices, however, a list of segments is no longer enough. We need to know which edges border the same region, which region lies on each side of an edge, and how to walk a boundary without searching the whole input. A doubly connected edge list (DCEL) stores exactly that topology.

A DCEL represents a planar embedding: a graph drawn so edges meet only at shared endpoints. Geometry supplies coordinates and predicates; the DCEL records the combinatorial answer to “what touches what?” Keeping those roles separate is powerful. Moving a vertex without changing edge order is geometric work. Splitting an edge, creating a face, or following a boundary is topological work.

One Edge Becomes Two Half-Edges

An undirected embedded edge separates two sides. The DCEL represents it by two oppositely directed half-edges. If half-edge $e$ runs from $u$ to $v$, then e.twin runs from $v$ to $u$. Direction lets each half-edge name the face immediately on one consistent side—conventionally its left side.

The three record types are:

• A vertex stores its coordinates and one incident outgoing half-edge.
• A half-edge stores origin, twin, next, prev, and face.
• A face stores one half-edge on its outer boundary and zero or more representatives of inner boundary cycles, or holes.

The destination of $e$ need not be stored: it is e.twin.origin. Likewise, a face boundary does not need an array of all its edges. Starting at one representative and repeatedly following next recovers the entire cycle.

The Local Invariants

A valid DCEL is held together by small identities that should be asserted after every mutation:

1. e.twin.twin is e.
2. e.next.prev is e and e.prev.next is e.
3. e.twin.origin is the destination of e.
4. Every half-edge encountered on a next cycle has the same incident face.
5. Every boundary walk closes at its starting half-edge without encountering None.
6. Each geometric edge owns exactly two half-edges, even when both sides belong to the same face, as happens for a bridge.

These invariants are local, but together they encode a global subdivision. They are also much more useful in tests than comparing a large serialized structure: a single broken splice is detected near its cause.

from dataclasses import dataclass, field
from typing import Optional

@dataclass(eq=False)
class Vertex:
    x: float
    y: float
    incident: Optional["HalfEdge"] = None

@dataclass(eq=False)
class Face:
    outer: Optional["HalfEdge"] = None
    holes: list["HalfEdge"] = field(default_factory=list)

@dataclass(eq=False)
class HalfEdge:
    origin: Vertex
    twin: Optional["HalfEdge"] = None
    next: Optional["HalfEdge"] = None
    prev: Optional["HalfEdge"] = None
    face: Optional[Face] = None

def boundary(start: HalfEdge):
    e = start
    while True:
        yield e
        e = e.next
        if e is start:
            return

eq=False matters here: records are nodes with identity and cyclic references, not recursively comparable values. Production code would also use integer IDs or handles, a coordinate policy, and explicit mutation methods rather than assigning pointers freely.

Faces, the Outer Face, and Holes

Every embedding has one unbounded outer face. It is a real face record, not the absence of a face. This prevents boundary edges from becoming special cases: their outward-pointing half-edges simply refer to the outer face.

A face can have several boundary components. Consider a square region containing an island-shaped hole. The face's outer cycle encloses the square; an inner cycle encloses the excluded island. With the “face lies to the left” convention, the outer boundary of a bounded face is counterclockwise and its hole boundaries are clockwise. The unbounded face has no outer component, but it may have several inner components—one around each disconnected embedded component.

Orientation is a useful consistency check, but not a substitute for topology. Signed area can classify a simple cycle under a known convention; nested cycles still require containment tests to determine which cycles are holes of which faces.

Traversal Recipes

To walk a face boundary, start from face.outer or a hole representative and follow next. The running time is proportional to the number of visited edges. To cross into the adjacent face, use e.twin.face. To circulate around a vertex, repeatedly apply e = e.twin.next (or the conventionally equivalent inverse rotation) until returning to the start. This enumerates incident half-edges in radial order without coordinate sorting at query time.

These primitives answer adjacency questions that raw segment arrays make expensive: list all faces touching a vertex, find the two faces separated by an edge, calculate a face perimeter, or flood-fill connected regions through selected edges.

Euler's Formula as a Topological Checksum

For a connected planar embedding, including the outer face,

$$V-E+F=2.$$

Intuitively, begin with one vertex and the outer face: $1-0+1=2$. Adding a tree edge and a new vertex increases both $V$ and $E$ by one, so the quantity stays fixed. Adding an edge between existing vertices that closes a cycle increases both $E$ and $F$ by one: the new edge splits one face into two. For $C$ connected components, the generalized identity is $V-E+F=1+C$.

Euler's formula cannot locate a corrupt pointer—two independent mistakes may cancel—but it catches many missing splits, forgotten faces, and duplicate edges. Use it after the local invariants, not instead of them.

Building a DCEL from Embedded Edges

Construction begins only after Part 6's sweep has noded the geometry: every proper crossing is a vertex, overlapping segments have been resolved according to policy, and no edge interior contains another endpoint.

1. Canonicalize equal coordinates and create one vertex record per location.
2. Create two twins for every embedded edge and assign their origins.
3. At each vertex, sort outgoing half-edges by polar angle using quadrant and orientation predicates rather than fragile atan2 ties.
4. Derive face cycles. If outgoing edges around a destination are counterclockwise, e.next is the appropriate predecessor or successor of e.twin in that radial order, depending on the chosen left-face convention. Pick one convention and test it on a triangle.
5. Walk every unassigned next cycle, create or associate face records, then use signed area and containment to group inner cycles with their containing faces.

The angular order is the bridge between coordinates and topology. If it is wrong at one vertex, next may jump across a face, producing bow-tie walks or merging regions that should be separate.

Updates Are Pointer Surgery

Splitting an edge at a new vertex replaces one twin pair by two twin pairs, splices each side into its old face cycle, and preserves both incident-face assignments. Inserting a chord between two vertices on one face creates two half-edge twins and two boundary cycles; one old face becomes two. Removing a non-bridge edge performs the reverse and merges its incident faces. Removing a bridge does not merge two faces, because both half-edges may already border the same face.

The safest update pattern is transactional: validate geometric preconditions, allocate all new records, splice a small neighborhood, update face representatives and vertex incident pointers, then run local invariants and Euler's check before committing. Never expose a half-updated DCEL to queries.

Common failures include forgetting to split at a crossing, confusing destination with origin, setting only one side of a reciprocal link, leaving a face representative pointing to a deleted edge, assuming every cycle is a separate face, and treating floating-point-near vertices as either equal or distinct inconsistently. Zero-length edges and duplicate geometric edges deserve rejection or an explicit multigraph policy. Robust predicates decide the embedding; pointer correctness preserves it.

From Representation to Overlay

The sweep line from Part 6 discovers where edges must be split; the DCEL turns those fragments into traversable regions. Part 8 will combine two such subdivisions. It will sweep their boundaries, insert cross-subdivision intersections, rebuild the local DCEL topology, propagate inside/outside labels across twins, and select faces for union, intersection, difference, or symmetric difference. Overlay is therefore not a separate magic trick: it is sweep-line noding plus disciplined DCEL traversal.