Quad-edge

A quad-edge data structure is a computer representation of the topology of a two-dimensional or three-dimensional map, that is, a graph drawn on a (closed) surface.

The fundamental idea behind the quad-edge structure is the recognition that a single edge, in a closed polygonal mesh topology, sits between exactly two faces and exactly two vertices.

Much like Winged Edge, quad-edge structures are used in programs to store the topology of a 2D or 3D polygonal mesh.

The mesh itself does not need to be closed in order to form a valid quad-edge structure.

The four edges are also given names, based on the vertices and faces: start-left, start-right, end-left, and end-right.