Characterization and detection of building patterns in cartographic data : two algorithms

Building patterns are important settlement structures in applications like automated generalization and spatial data mining. Previous investigations have focused on a few types of building patterns (e.g. collinear building alignments); while many other types are less discussed. In order to get better known of the building patterns available in geography, this paper studies existing topographic maps at large to medium scales, and proposes and discusses a comprehensive typology of building patterns, their distinctions and characteristics. The proposed typology includes linear alignments (i.e. collinear, curvilinear, align-along-road alignments) and nonlinear clusters (grid-like and unstructured patterns). We concentrate in this paper on two specific building structures: align-along-road alignment and unstructured clusters. Two graph-theoretic algorithms are presented to detect these two types of building patterns. The approach bases itself on auxiliary data structures such as Delaunay triangulation and minimum spanning trees for clustering; several rules are used to refine the clusters into specific building patterns. Finally, the proposed algorithms are tested against a real topographic dataset of the Netherlands, which shows the potential of the two algorithms.