Automatic reasoning for geometric constraints in 3D city models with uncertain observations

This paper presents a novel approach to automated geometric reasoning for 3D building models. Geometric constraints like orthogonality or parallelity play a prominent role in man-made objects such as buildings. Thus, constraint based modelling, that specifies buildings by their individual components and the constraints between them, is a common approach in 3D city models. Since prototyped building models allow one to incorporate a priori knowledge they support the 3D reconstruction of buildings from point clouds and allow the construction of virtual cities. However, high level building models have a high degree of complexity and consequently are not easily manageable. Interactive tools are needed which facilitate the development of consistent models that, for instance, do not entail internal logical contradictions. Furthermore, there is often an interest in a compact, redundancy-free representation. We propose an approach that uses algebraic methods to prove that a constraint is deducible from a set of premises. While automated reasoning in 2D models is practical, a substantial increase in complexity can be observed in the transition to the three-dimensional space. Apart from that, algebraic theorem provers are restricted to crisp constraints so far. Thus, they are unable to handle quality issues, which are, however, an important aspect of GIS data and models. In this article we present an approach to automatic 3D reasoning which explicitly addresses uncertainty. Hereby, our aim is to support the interactive modelling of 3D city models and the automatic reconstruction of buildings. Geometric constraints are represented by multivariate polynomials whereas algebraic reasoning is based on Wu’s method of pseudodivision and characteristic sets. The reasoning process is further supported by logical inference rules. In order to cope with uncertainty and to address quality issues the reasoner integrates uncertain projective geometry and statistical hypothesis tests. Consequently, it allows one to derive uncertain conclusions from uncertain premises. The quality of such conclusions is quantified in a way which is sound both from a logical and a statistical perspective.