Optimal and Topologically Safe Simplification of Building Footprints.
In: A. E. Abbadi, D. Agrawal, M. Mokbel und P. Zhang, editors, Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS'10), November 2-5, 2010, San Jose, CA, USA, pages 192-201. 2010.
J.-H. Haunert and A. Wolff.
[doi] [PDF] http://www.bibsonomy.org/bibtex/209d394785e27481bff5cd884a42c844e/haunert?format=bibtex[BibTeX]
We present an optimization approach to simplify sets of building footprints represented as polygons. We simplify each polygonal ring by selecting a subsequence of its original edges; the vertices of the simplified ring are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of all output edges subject to a user-defined error tolerance. Since we earlier showed that the problem is NP-hard when requiring non-intersecting simple polygons as output, we cannot hope for an efficient, exact algorithm. Therefore, we present an efficient algorithm for a relaxed problem and an integer program (IP) that allows us to solve the original problem with existing software. Our IP is large, since it has $O(m^6)$ constraints, where $m$ is the number of input edges. In order to keep the running time small, we first consider a subset of only $O(m)$ constraints. The choice of the constraints ensures some basic properties of the solution. Constraints that were neglected are added during optimization whenever they become violated by a new solution encountered. Using this approach we simplified a set of 144 buildings with a total of 2056 edges in 4.1 seconds on a standard desktop PC; the simplified building set contained 762 edges. During optimization, the number of constraints increased by a mere 13 %. We also show how to apply cartographic quality measures in our method and discuss their effects on examples.
Detecting Symmetries in Building Footprints by String Matching.
In: S. Geertman, W. Reinhardt and F. Toppen, editors, Advancing Geoinformation Science for a Changing World - Proc. 14th AGILE International Conference on Geographic Information Science, series Lecture Notes in Geoinformation and Cartography, pages 319-336. Springer, Berlin, Germany, 2011.
J.-H. Haunert.
[doi] [PDF] [BibTeX]
This paper presents an algorithmic approach to the problem of finding symmetries in building footprints. The problem is motivated by map generalization tasks, for example, symmetry-preserving building simplification and symmetry-aware grouping and aggregation. Moreover, symmetries in building footprints may be used for landmark selection and building classification. The presented method builds up on existing methods for symmetry detection in polygons that use algorithms for string matching. It detects both axial symmetries and repetitions of geometric structures. In addition to the existing string-matching approaches to symmetry detection, we consider the problem of finding partial symmetries in polygons while allowing for small geometric errors. Moreover, we discuss how to find optimally adjusted mirror axes and to assess the quality of a detected mirror axis using a least-squares approach. The presented approach was tested on a large building data set of the metropolitan Boston area. The dominant symmetry relations were found. Future work is needed to aggregate the obtained symmetry relations, for example, by finding sets of mirror axes that are almost collinear. Another open problem is the integration of information on symmetry relations into algorithms for map generalization.
