An octree-based implementation of directional operators in a 3D Spatial Query Language for Building Information Models

In a current research project, our group is developing a 3D Spatial Query Language that enables the spatial analysis of Building Information Models and the extraction of partial models that fulfil certain spatial constraints. Among other features, the spatial language includes directional operators, i.e. operators that reflect the directional relationships between 3D spatial objects, such as northOf, southOf, eastOf, westOf, above and below. The paper presents in-depth definitions of the semantics of these operators by means of point set theory. It further gives an overview on the possible implementation of directional operators using a new space-partitioning data structure called slot-tree, which is derived from the objects’ octree representation. The slot-tree allows for the application of recursive algorithms that successively increase the discrete resolution of the spatial objects employed and thereby offer the possibility for a trade-off between computational effort and required accuracy