A GRAPH-BASED APPROACH FOR HIGHER ORDER GIS TOPOLOGICAL ANALYSIS I 
ir 
J.-P. de Almeida™® *, J. G. Morley, I. J. Dowman? o 
d 
* Dept. of Geomatic Engineering, University College London, Gower Street, LONDON WCIE 6BT, UK W 
(almeida, jmorley, idowman)(gge.ucl.ac.uk d 
http://www.ge.ucl.ac.uk/ s 
? Section of Geomatic Engineering, Dept. of Mathematics, Faculty of Science and Technology, University of Coimbra, ; 
Largo D. Dinis, Apartado 3008, 3001-454 COIMBRA, Portugal p 
http://www.mat.uc.pt/ ie 
be 
th 
KEY WORDS: LiDAR, Urban, GIS, Algorithms, Analysis, Interpretation, Understanding 
1. 
ABSTRACT: C: 
SC 
Retrieving structured information from an initial random collection of objects may be carried out by understanding the spatial Cc 
arrangement between them, assuming no prior knowledge about those objects. As far as topology is concerned, contemporary of 
desktop GIS packages do not generally support further analysis beyond adjacency. Thus, one of the original motivations of this work fa 
was to develop new ideas for scene analysis by building up a graph-based technique for better interpretation and understanding of B; 
spatial relationships between GIS vector-based objects beyond its first level of adjacency; the final aim is the performance of some th 
kind of local feature organization into a more meaningful global scene by using graph theory. As the example scenario, a LiDAR ca 
data set is being used to test the technique that we plan to develop and implement. After the generation of the respective TIN, two fa 
different binary classifications were applied to the TIN facets (based on two different slope thresholds) and TIN facets have been de 
aggregated into homogeneous polygons according to their slope characteristics. A graph-based clustering procedure inside these of 
polygonal regions, by establishing a neighbourhood graph, followed by the delineation of cluster shapes and the derivation of cluster be 
characteristics in order to obtain higher level geographic entities information (regarding sets of buildings, vegetation areas, and say, ec 
land-use parcels) is object of further work. The results we are expecting to obtain might be useful to support land-use mapping, fu 
image understanding or, generally speaking, to support clustering analysis and generalization processes. 19 
1. INTRODUCTION AND MOTIVATION understanding of topological relationships between GIS vector- 
based objects beyond the first level of adjacency. 2.1 
Interpretation and analysis of spatial phenomena is a highly 
time consuming and laborious task in several fields of the 1.2 Graph theory Th 
Geomatics world. This is particularly true given the more an 
accurate but also the larger and larger spatial data sets that are Other initial interest was to investigate the possible use of fro 
being acquired with the new technologies that are continuously graph theory for this purpose. This mathematical framework is lev 
being developed. That is why the automation of those tasks is said to be fairly powerful and elegant based only on a few basic So 
extraordinarily simple principles (Temperley, 1981). Indeed, a 
several authors (including Laurini and Thompson, 1992) poi 
maintain that this particular tool is extremely valuable and 
efficient in storing and describing the spatial structure of 
especially needed in areas such as GIS amongst others (Anders 
et al., 1999). 
The aim of retrieving structured information, translated into 
  
  
more meaningful homogeneous regions (say, land-use parcels), 
from an initial unstructured data set may be achieved by 
identifying meaningful structures within the initial random 
collection of objects and by understanding the spatial 
arrangement between them, ie, by understanding the 
topological relationships between the identified structures. 
1.1 Topology 
Topology is a particularly important research area in the field of 
GIS for it is a central defining feature of a geographical 
information system. Generally speaking, as far as topological 
relationships between geographical entities are concerned, 
contemporary desktop GIS packages do not support further 
information beyond the first level of adjacency (Theobald, 
2001). Therefore, one of the first motivations of the work 
geographical entities and their spatial arrangement which, after 
stripping away their geometric properties, are seen in a GIS 
environment as points, lines or areas. Theobald (2001) adds that 
concepts of graph theory allow us to extend the standard notion 
of adjacency. To date, graph theory has been used in different 
applications in a wide range of fields to represent connections 
and relationships between spatial entities. 
1.3 LiDAR data 
In most of the applications developed so far, the starting 
situation is to some extent a meaningful data set in terms of the 
scene. We seek to explore and investigate whether it is possible 
to start at a level further back with an unattributed data set and, 
hence, we are assuming no prior knowledge of the spatial 
entities. 
  
; E Hs ; , : As ¢ 
described in this paper was also to develop new ideas for scene As the example scenario LiDAR data are being used to test the 3D 
analysis by building up in a different way a technique for better graph-based technique that we plan to develop and implement M 
topa 
  
* Corresponding author. 
1048