Specification and implementation of directional operators in a 3D spatial query language for building information models

A spatial query language enables the spatial analysis of building information models and the extraction of partial models that fulfill certain spatial constraints. Among other features, the developed spatial query 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 two new directional models for extended 3D objects, the projection-based and the halfspace-based model, by using point-set theory notation. It further describes the possible implementation of directional operators using a newly developed 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 enables the user to trade-off between computational effort and the required accuracy. The article also introduces detailed investigations on the runtime performance of the developed algorithms. (C) 2008 Elsevier Ltd. All rights reserved.