A three-dimensional data model for representing topological relationships between spatial entities in built-environments

This research has developed a topological data mode, the Node-Relation Structure (NRS), for representing spatial relationships between 3D spatial entities in built-environments by resolving complex geometric computational problems differently from current topological models representing local neighborhood relations. The NRS represents the spatial relations by two data models. One is a combinatorial data model (CDM), which is a logical data model to represent topological relations of 3D objects. The other is a geometric network model (GNM) to implement spatial accesses in the NRS using searching path algorithms. The geometric network model for the NRS is constructed by converting the combinatorial data model representing the connectivity relationships between 3D entities. The combinatorial data model is conceptualized by three basic elements, which are Poincare Duality, graph theory and multi-scale data representation. In order to simplify the complex spatial relationships between 3D entities, the NRS is constructed by Poincare Duality, which transforms ‘3D to 2D relations’ in primal space to ‘0D to 1D relations’ in dual space. Because the CDM consists of 0-cells and 1-cells, the model is utilized by graph theory. Using graph methods, the sub-graph of the NRS is consolidated to a high-level node, which is called a Master_node for hierarchical data representations. In order to implement 3D spatial queries in the NRS based upon shortest path operations, the combinatorial network model representing the connectivity relations needs to be transformed into the geometric network model. One key step in the process is to identify linear features from a simple polygon (a hallway in this study) by using Medial Axis Transformation. In implementing the medial axis algorithms in this study, there are two types of artifacts, which are intersection artifacts and a line end artifact, so this research develops the Straight Medial Axis Transformation (S-MAT) algorithm for a simple polygon. The straight medial axis is constructed with the angular bisectors of each pair of neighboring edges. For developing the S-MAT algorithm whose entire procedure takes O(n2) time, three properties are defined. Using the straight medial axis transformation, the hallway is transformed into the linear features. Each node representing 3D spatial units is projected and connected onto the medial axis if there is a connectivity relation. The time required for the projection of each node onto the linear features is O(nm), where n is the number of nodes and m is the number of edges in the medial axis. Using the reconstructed geometric network model, therefore the complex topologic relations among 3D spatial objects are analyzed. The NRS system is designed as a module to be a major component of 3D GISs in the Visual Basic development environment for implementing the NRS. The NRS system consists of two major modules, which are Data Generation Module (DGM) and 3D NRS Implementation Module (3D-NRSIM). Finally, the study demonstrates the use of the NRS system for analyzing the complex connectivity relationships among 3D objects in built-environments through the modified Dijkstra's algorithm.