Consistent Operations on a Spatial Data Structure

Geometric objects such as polygons, line segments, and points may have manifold relations among each other, i.e., order, adjacency, connectivity, etc., and may be stored in a database. For the design of the spatial data structure and in order to preserve consistency when manipulating the data, we propose a graph grammar approach. All consistent states are described by a structure graph, and the manipulation rules are given by productions where intersection problems as well as topologic properties have to be solved. By appropriately modeling the behavior of geographic data, consistency is preserved at all times. This eliminates the tedious case of recovering a geographic database after an inconsistency has been detected.