DERIVING SPATIAL RELATIONS OF BUILDING FEATURES USING CONDITIONAL DELAUNAY TRIANGULATION TO SUPPORT AUTOMATED MAP GENERALIZATION

Hits: 82
Research areas:
Year:
2016
Type of Publication:
In Proceedings
Keywords:
data enrichment, Delaunay triangulation, constrained Delaunay triangulation, automated map generalization, proximity relations
Authors:
S, Rupasinghe K. A. B.
Abstract:
The paper first reviews the existing data enrichment techniques for automated map generalization based on several spatial data structures. Next, it provides a broad explanation of the well-known triangulation data structure found in the literature for enriching spatial relations of building polygons to be used in automated map generalization. This paper then presents a novel approach to enrich spatial relations for retrieving neighbourhood and proximity relations of building polygons using Delaunay triangulation, taking into account the edges of buildings as constraints based on a new principle called ‘non-edge intersection’ to support automated map generalization. This triangulation method is termed as conditional Delaunay triangulation (CnDT) since it respects empty-circumcircle criterion in generating triangles, enforcing edges of buildings as constraints in the triangulation process. The main significance of this triangulation method is the ability to derive explicit neighbourhood relations between building polygons without densification of edges of building geometries by adding new vertices into source data or interpolating artificial vertices on edges of buildings in the triangulation process. These neighbourhood relations enable extracting proximity relations efficiently direct from the object identification numbers tagged to three nodes of each triangle of the triangulation. The implementation of the approach is presented and described with several graphs including results to generate CnDT and the proximity relations of building polygonal features on the raw data set, ranging from simple geometries to complex geometries comprising of contiguous edges, polygon holes, and arbitrary split edges. Also, the results of the triangulation are compared with those obtained using the Constrained Delaunay triangulation method. Finally, the advantages and disadvantages of the proposed algorithm are discussed against the existing triangulation algorithms used for subsequent automated map generalization process.
Full text: Ab 0540.pdf [Bibtex]
You are here: Home ACRS ACRS Overview Proceedings DERIVING SPATIAL RELATIONS OF BUILDING FEATURES USING CONDITIONAL DELAUNAY TRIANGULATION TO SUPPORT AUTOMATED MAP GENERALIZATION