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.

doi:10.1145/1869790.1869819

@inproceedings{haunertwolff2010,
    abstract = {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.},
    author = {Haunert, J.-H. and Wolff, A.},
    booktitle = {Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10)},
    doi = {10.1145/1869790.1869819},
    file = {HaunertWolff2010.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertWolff2010.pdf:PDF},
    pages = {192--201},
    timestamp = {2011-11-07T12:01:05.000+0100},
    title = {Optimal and Topologically Safe Simplification of Building Footprints},
    url = {http://dl.acm.org/citation.cfm?doid=1869790.1869819},
    year = {2010}
}

Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.

doi:10.1080/13658810903401008

@article{haunertwolff2010b,
    abstract = {Topographic databases normally contain areas of different land cover classes, commonly defining a planar partition, that is, gaps and overlaps are not allowed. When reducing the scale of such a database, some areas become too small for representation and need to be aggregated. This unintentionally but unavoidably results in changes of classes. In this article we present an optimisation method for the aggregation problem. This method aims to minimise changes of classes and to create compact shapes, subject to hard constraints ensuring aggregates of sufficient size for the target scale. To quantify class changes we apply a semantic distance measure. We give a graph theoretical problem formulation and prove that the problem is NP-hard, meaning that we cannot hope to find an efficient algorithm. Instead, we present a solution by mixed-integer programming that can be used to optimally solve small instances with existing optimisation software. In order to process large datasets, we introduce specialised heuristics that allow certain variables to be eliminated in advance and a problem instance to be decomposed into independent sub-instances. We tested our method for a dataset of the official German topographic database ATKIS with input scale 1:50,000 and output scale 1:250,000. For small instances, we compare results of this approach with optimal solutions that were obtained without heuristics. We compare results for large instances with those of an existing iterative algorithm and an alternative optimisation approach by simulated annealing. These tests allow us to conclude that, with the defined heuristics, our optimisation method yields high-quality results for large datasets in modest time.},
    author = {Haunert, J.-H. and Wolff, A.},
    doi = {10.1080/13658810903401008},
    file = {HaunertWolff2010b.pdf:http\://www1.informatik.uni-wuerzburg.de/pub/haunert/pdf/HaunertWolff2010b.pdf:PDF},
    journal = {International Journal of Geographical Information Science},
    number = {12},
    pages = {1871--1897},
    timestamp = {2011-11-07T12:01:05.000+0100},
    title = {Area aggregation in map generalisation by mixed-integer programming},
    url = {http://www.informaworld.com/smpp/content~db=all~content=a930246337~tab=content},
    volume = {24},
    year = {2010}
}

Building reconstruction and building model generation nowadays receives more and more attention. In this context models such as formal grammars play a major role in 3D geometric modelling. Up to now, models have been designed manually by experts such as architects. Hence, this paper describes an Inductive Logic Programming based approach for learning semantic models and grammar rules of buildings and their parts. Due to their complex structure and their important role as link between the building and its outside, stairs are presented as an example. ILP is introduced and applied as machine learning method. The learning process is explained and the learned models and results are presented.

@inproceedings{dehbi2010,
    abstract = {Building reconstruction and building model generation nowadays receives more and more attention. In this context models such as formal grammars play a major role in 3D geometric modelling. Up to now, models have been designed manually by experts such as architects. Hence, this paper describes an Inductive Logic Programming based approach for learning semantic models and grammar rules of buildings and their parts. Due to their complex structure and their important role as link between the building and its outside, stairs are presented as an example. ILP is introduced and applied as machine learning method. The learning process is explained and the learned models and results are presented.},
    author = {Dehbi, Y. and Schmittwilken, J{\"{o}}rg and Pl{\"{u}}mer, L.},
    booktitle = {Proc. 24th Workshop on Constraint Logic Programming (WLP 2010)},
    pages = {45--56},
    publisher = {German University in Cairo},
    title = {Learning Semantic Models and Grammar Rules of Building Parts},
    year = {2010}
}