SPATIAL ACCESS METHODS FOR ORGANIZING LASERSCANNER DATA 
Thomas Brinkhoff 
Institute for Applied Photogrammetry and Geoinformatics (IAPG) 
FH Oldenburg/Ostfriesland/Wilhelmshaven (University of Applied Sciences) 
D-26121 Oldenburg, Germany 
Thomas.Brinkhoff(g)fh-oldenburg.de 
Commission IV, WG IV/1 
KEY WORDS: Laser scanning, Data Structures, Database, Performance, Processing 
ABSTRACT: 
Laserscanning produces large sets of multidimensional point data, which demand for an effective and efficient organization and 
storage. Adequate data structures must perform specific spatial queries and operations in order to support the computation and / or 
the construction of surface models. Because of their increasing size, it is not advisable to organize the clouds of points by main- 
memory data structures. Such an approach would lead to long loading times and misses scalability. Instead, persistent data structures 
are desirable. In this paper, the usage of multidimensional spatial access methods are investigated for organizing laserscanner data. 
Such access methods have originally been developed for storing and indexing geographic data in spatial database systems and 
Geographical Information Systems. Point access methods based on hierarchical hash trees are one important class of such access 
methods. Typical examples for hash trees are the BANG file and the buddy tree. Rectangle access methods are another class of 
relevant access methods. The R-tree and its variants are the most important representative of this class. R-trees are typically used by 
commercial spatial database systems. All data structures mentioned before are fully dynamic, i.e. they support arbitrary sequences of 
insertions, modifications and deletions. They allow a persistent storage of multidimensional points and preserve spatial proximity 
locally, i.e. within (database or file) blocks. The performance of the above point and rectangle access methods is investigated and 
compared for storing and querying large clouds of points representing buildings. The examination identifies those access methods 
that allow a fast construction of the data structure as well as an efficient support of relevant spatial queries. For some queries, 
however, a local preservation of spatial proximity is not sufficient. The extraction of points for overview purposes is an example for 
such a query. Therefore, different approaches for a global preservation of spatial proximity are introduced and experimentally 
investigated. 
1. INTRODUCTION > relational and object-oriented) database systems as an index. 
Therefore, they are also called index structures. However, 
Laserscanning gains more and more importance in the last few conventional index structures are optimized for one- 
years. It allows the simple and inexpensive measurement of dimensional data types like numbers and character strings. They 
spatial objects like fagades or the interior of buildings. cannot be used (without modification) for spatial data. For this 
Laserscanning produces large sets of multidimensional point purpose, spatial index structures (also called spatial access 
data, which demand for an effective and efficient organization methods) have been developed for spatial database systems and 
and storage (Niemeier & Kern, 2001) The measurements Geographical Information Systems (Rigaux et al., 2002). One 
provide immediately Cartesian coordinate values (x,y,z) and — category of spatial index structures are point access methods, 
for some laserscanners — the intensity of the received signal. which allow the dynamic organization of multidimensional 
Therefore, the result of a measurement is a set of three- or four- points on secondary storage. Rectangle access methods are 
dimensional points. another class of spatial access methods supporting extended 
objects, especially multidimensional rectangles, but also non- 
Because of the large data volume — several millions of points extended objects, i.c. multidimensional points. All types of 
with increasing tendency — it is not advisable to store the points spatial index structures support the efficient processing of 
as conventional points in a CAD program (Schwermann & spatial queries. 
Effkemann, 2002). In general, the approach to maintain the 
cloud of points in main memory has several disadvantages: In this paper, the question is investigated whether spatial access 
e Such an approach requires a long time for loading the data methods are suitable for storing point clouds produced by 
from secondary storage (like hard disks). laserscanners. Section 2 presents different spatial access 
e Main memory storage shows a bad scalability because it methods. The main focus is on so-called hash trees and R-trees. 
swaps (after exceeding a threshold) parts of the memory In section 3, we consider the use of such index structures for 
onto the slow secondary storage. data produced by.laserscanners. The paper concludes with a 
short summary and an outlook to future work. 
An alternative is the usage of persistent data structures. Such 
data structures store the data on secondary storage and allow 
reading only (the required) parts of the data. Such data 
structures have been developed to be used in (relational, object- 
98 
ac 
SC 
di 
in 
tv 
he 
lea 
Hc 
(1.« 
of 
Do 
exi 
val 
abc 
pre 
ran 
nai