Ellul, C.; (2008) Functionality and performance: two important considerations when implementing topology in 3D. Doctoral thesis , University of London.

PDF U591207.pdf Download (49MB)

Abstract

This thesis contributes to the understanding of the use of topology in analysing 3D spatial data, focussing in particular on two aspects of the problem - what binary topological analysis functionality is required in a commercial 3D Geographical Information System (GIS), and how should this functionality be implemented to achieve the most efficient query performance. Topology is defined as the identification of spatial relationships between adjacent or neighbouring objects. The first stage of this research, a review of applications of topology, results in a generic list of requirements for topology in 3D. This was carried out in parallel with a review of topological frameworks and the relationships identified by one of the frameworks, Egenhofer and Herring's 9-Intersection, selected for implementation. Three generic binary relationship queries are identified (Find Objects with a Specific Relationship, Find Intersecting Objects and What Relationship is there Between These Objects) and a mechanism described to allow these to be adapted to specific application terminology. Approaches to the implementation of 3D binary topological queries include the use of data structures and an As-Required calculation, where computational geometry algorithms are run to determine relationships each time the user runs a query. The Three-Dimensional Formal Data Structure (3DFDS) was selected as a representative example of a Boundary-Representation (B- Rep) structure in GIS. Given the number of joins to be traversed when identifying binary relationships from a B-Rep structure, along with the requirement to query additional containment exception tables, an alternate structure, the Simplified Topological Structure (STS), was proposed to improve binary query performance. Binary relationship queries were developed and comparative performance tests carried out against 3DFDS, STS and a Proxy for the As-Required calculation, using a 1.08 million object test dataset. Results show that STS provides a significant performance improvement over 3DFDS. No definitive conclusion could be drawn when comparing STS with the Proxy for the As-Required approach.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as XMLCSVJSON

Downloads by country - last 12 months

Export as CSVXMLJSON

Archive Staff Only

View Item