quadedges

Quadedge is a data structure used in computational geometry to represent subdivisions of a plane into regions, such as triangles or polygons. It was introduced by Guibas and Stolfi in 1985 as an alternative to the doubly connected edge list (DCEL) for representing planar subdivisions. The primary advantage of quadedge is its simplicity and efficiency in handling operations like flipping edges, which is useful in algorithms like Delaunay triangulation and Voronoi diagram construction.

A quadedge consists of four directed edges, each pointing to its successor and predecessor around a common vertex. This structure allows for efficient traversal and manipulation of the subdivision. Each quadedge can be thought of as a fundamental unit that represents a pair of dual edges in the subdivision: one in the primal graph (connecting vertices) and one in the dual graph (connecting faces).

The quadedge data structure supports a variety of operations, including:

- Splitting an edge to create a new vertex.

- Flipping an edge to change the connectivity of the subdivision.

- Merging edges to remove a vertex.

These operations are performed in constant time, making quadedge highly efficient for dynamic planar subdivisions. The structure is particularly useful in algorithms that require frequent edge flips, such as those used in computational geometry and graphics.

In summary, quadedge is a versatile and efficient data structure for representing and manipulating planar subdivisions. Its simplicity and constant-time operations make it a valuable tool in various computational geometry applications.