3D Hilbert Space Filling Curves in 3D City Modeling for Faster Spatial Queries

3D Hilbert Space Filling Curves in 3D City Modeling for Faster Spatial Queries

Uznir Ujang (Department of Geoinformation, Faculty of Geoinformation and Real Estate, Universiti Teknologi Malaysia, Johor, Malaysia), Francois Anton (Department of Geoinformation, Faculty of Geoinformation and Real Estate, Universiti Teknologi Malaysia, Johor, Malaysia and Department of Geodesy, National Space Institute, Denmark Technical University, Denmark), Suhaibah Azri (Dept. of Geoinformation, Faculty of Geoinformation and Real Estate, Universiti Teknologi Malaysia, Johor, Malaysia), Alias Abdul Rahman (Dept. of Geoinformation, Faculty of Geoinformation and Real Estate, Universiti Teknologi Malaysia, Skudai, Johor, Malaysia) and Darka Mioc (Department of Geodesy, National Space Institute, Denmark Technical University, Lyngby, Denmark)
Copyright: © 2014 |Pages: 18
DOI: 10.4018/ij3dim.2014040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The advantages of three dimensional (3D) city models can be seen in various applications including photogrammetry, urban and regional planning, computer games, etc. They expand the visualization and analysis capabilities of Geographic Information Systems on cities, and they can be developed using web standards. However, these 3D city models consume much more storage compared to two dimensional (2 D) spatial data. They involve extra geometrical and topological information together with semantic data. Without a proper spatial data clustering method and its corresponding spatial data access method, retrieving portions of and especially searching these 3D city models, will not be done optimally. Even though current developments are based on an open data model allotted by the Open Geospatial Consortium (OGC) called CityGML, its XML-based structure makes it challenging to cluster the 3D urban objects. In this research, the authors propose an opponent data constellation technique of space-filling curves (3D Hilbert curves) for 3D city model data representation. Unlike previous methods, that try to project 3D or n-dimensional data down to 2D or 3D using Principal Component Analysis (PCA) or Hilbert mappings, in this research, they extend the Hilbert space-filling curve to one higher dimension for 3D city model data implementations. The query performance was tested for single object, nearest neighbor and range search queries using a CityGML dataset of 1,000 building blocks and the results are presented in this paper. The advantages of implementing space-filling curves in 3D city modeling will improve data retrieval time by means of optimized 3D adjacency, nearest neighbor information and 3D indexing. The Hilbert mapping, which maps a sub-interval of the ([0,1]) interval to the corresponding portion of the d-dimensional Hilbert's curve, preserves the Lebesgue measure and is Lipschitz continuous. Depending on the applications, several alternatives are possible in order to cluster spatial data together in the third dimension compared to its clustering in 2 D.
Article Preview

Visualization of three dimensional (3D) objects becomes more widespread in developments (see Behley, and Steinhage, (2009), Jin and Bian (2006) and Liu, and Fang (2009)). This can be seen from the demand in 3 D based applications (see Freitas, Sousa, and Coelho (2010) and Zhang, Fang, and Jing (2009)). Visualization of 3D objects can support a more realistic view as in the real environment than the two-dimensional (2 D) visualization. 3D view of a building model is more realistic compared to 2D floor plan of a building in a navigation application.

In commercial software development, private companies are competing in developing tools that are capable of managing 3D cities. ESRI (CityEngine), Bentley (Bentley’s Map V8i) and Google (Google Earth) offer users the capability to create, visualize and measure 3D cities in their products (Jazayeri, 2012).

Since quite a number of 3D city model formats are available, there is a need for standardizing the 3D city model format for various applications. City Geography Markup Language (CityGML) is an example of an exchange standard format for 3D city models (see Figure 1). It consists of different Levels of Details (LOD); LOD0, LOD1, LOD2 and LOD3. Different LODs reflect different 3 D spatial information details. The higher the LoD, more object detail and geometry is included. This common information model is the first standard related to 3D city models (Jazayeri, 2012).

Figure 1.

LoD2 building illustration: CityGML feature structure as UML instance diagram (taken from Gro¨ger, and Plu¨mer (2012))

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 4 Issues (2017): 2 Released, 2 Forthcoming
Volume 5: 4 Issues (2016)
Volume 4: 4 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2013)
Volume 1: 4 Issues (2012)
View Complete Journal Contents Listing