A Unified Spatial Data Structure for GIS

  • Maciej Dakowicz

    Student thesis: Doctoral Thesis


    Most GIS systems use separate thematic "layers" to store different types of spatial data. Each of them contains specific characteristics of the area, so there are separate layers for the distribution of buildings, the road network or the relief of the terrain. The spatial information used in GIS can be grouped into four main groups: polygonal maps, terrain models, networks and discrete, unconnected objects. Polygonal maps and terrain models are considered to be "field" models of space, covering the whole map, so there is some kind of information available at every location. On the other hand, networks and discrete objects are representations of the "object" model of space, in which the map is populated by entities and the space between them is empty. Choropleth maps are the most common examples of polygonal maps and the three main representations of terrain models are Triangular Irregular Networks (TINs), grids and contour lines. Networks consist of connected edges, while discrete objects can be points, lines or polygons. In networks, polygonal maps and surfaces there is some model of connectivity available. Polygons are adjacent to each other, as are the elements in terrain models. Network data is connected along the edges and junctions are defined. Unconnected objects need have no connectivity information, but in that case the possible spatial queries are limited.

    The layers can be stacked on top of each other to perform various operations and analyses on them. However, there is no consistent method applicable to all data types because GIS has traditionally separated field and object layers and used different data structures to represent them. This thesis presents a unified spatial data model for these most common types of spatial information and intends to show that it has clear advantages for geographical analysis. The idea is to represent discrete object models as fields, so there is information available at all locations. The model is based on the Voronoi Diagram (VD) and the dual Delaunay Triangulation (DT), two well studied geometric structures. Depending on the application it may be appropriate to represent the data on the map by the simple VD/DT, or their derivatives - the Constrained DT (CDT), the Line Segment VD (LSVD) or the crust and the skeleton. All of these are directly related to each other and may be handled in a single manner in the computer. Algorithms and the storage of these various forms of the VD using the quad-edge data structure is described. This structure may be updated locally, and dynamic algorithms for each of these representations are presented. This allows for the development of a common interactive framework for what are traditionally considered to be distinct data types.

    The unified model is illustrated by a variety of GIS applications, and the implementation of several traditional GIS operations and queries is discussed.
    Date of AwardJun 2009
    Original languageEnglish


    • Geographic information systems

    Cite this