quadedge

Quadedge is a compact topological data structure for representing subdivisions of two-dimensional manifolds, such as the Euclidean plane or curved surfaces. It was introduced by Leonidas Guibas and Jorge Stolfi in their 1985 work on general planar subdivisions. The quadedge unifies the storage of vertices, edges, and faces and supports robust, local topology updates.

The core concept is the quadedge, a collection of four directed half-edges that together encode an undirected edge and its surrounding faces and vertices. Each half-edge stores its origin vertex, a reference to the next half-edge around its left face, and a reference to its symmetric half-edge. The four half-edges in a quadedge are interrelated by rotation operators (often labeled rot and invrot) that traverse the primal and dual graphs, allowing efficient navigation around vertices, edges, and faces.

Operations such as makeEdge, splice, connect, and deleteEdge (and edge flips in triangulations) are defined to preserve the topological consistency of the subdivision. The quadedge abstraction makes local mesh edits straightforward and reversible, which is advantageous for dynamic triangulations and mesh optimization.

Applications include planar triangulations, polygon meshes, Voronoi diagrams, and Delaunay computations, where maintaining a consistent topology during edits is important. The quadedge is conceptually related to other topological representations such as the DCEL and half-edge data structures, but it emphasizes the symmetric, quad-based primitive that encodes both primal and dual information in a uniform manner.