Spatial Data Structures

From VoroWiki

Much discussion has been expended in the last two decades on the appropriate data structures to handle map data-specifically the relationships between polygons, arcs and nodes on a thematic map coverage. The layman may be excused for (1) being confused by the plethora of protagonists of various schemes and (2) wondering if they are all that different anyhow.

The discussion can be carried on at at least two levels. At the implementation level concern may be over word length, record types and file structures-these do not concern us here. At the data abstraction level we wonder, for example, whether we should create node records informing us that a particular location forms the junction of three edges (arcs) and three polygons, or if preserving the polygon numbers on each side of an arc will serve just as well. Follow the link to PAN graphs, which facilitates discussion of these object relationship issues. Also see Gold (1988)^[1] for more details.

Triangle-based data structure

Winged-edge

Half-edge

Quad-edge

The quad-edge data structure Guibas and Stolfi (1985)^[2] was developed to represent simultaneously the primal and dual subdivisions of a 2-manifold, and also to navigate from edge to edge in these subdivisions. Each quad-edge represents one geometrical edge of a subdivision, and this edge is decomposed into four directed edges: two in the primal, and their two respective dual edges. Each directed edge is represented by a quad, which, in a given subdivision, will either point to one vertex or to a face; in the dual, a quad points to the dual of what it is pointing to in the primal. Its advantages are firstly that there is no distinction between the primal and the dual representation (it is symmetric with respect to edges and faces/polygons), and secondly that all operations are performed as pointer operations only, thus giving an algebraic representation to its operations. The figure shows the basic structure, with four branches (quads) for each edge of the graph being stored (the dual edges are not drawn), one for each of the incident vertices or faces. There are three pointers on each quad: one to the vertex or face object (org), one to the next anticlockwise quad-edge around that object (next), and one to link the four quads together in a loop (rot). Thus all vertices or faces have complete topological loops around them. Notice that the rot operation actually permits us to navigate between the primal and the dual subdivisions.

Only two commands are used to modify a graph: MakeEdge to create a new edge on a manifold, and Splice to connect/disconnect quad-edges together (see the figure). In the simplest case, Splice connects two separate next loops, joining the two nodes together, and at the same time splitting the next loop around the common face. Splice is its own inverse.

The \emph{Splice} operator.

The quad-edge data structure and some basic operators (only one subdivision is represented). The starting quad $q$ is the black quad, and the resulting quads are grey.

Quad-edge triangulation

Quad-edge structure

See also

• Extension to 3D of the Quad-edge Structure

References

1. ↑ Gold, C.M. (1988), 'PAN Graphs: an aid to GIS Analysis', International Journal of Geographical Information Systems 2, 29-42.
2. ↑ Guibas, L.J. & Stolfi, J. (1985), 'Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams', ACM Transactions on Graphics 4, 74-123.