Paper Info
Title
Optimal and topologically safe simplification of building footprints
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(m6) 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.
Year
DOI
Venue
2010
10.1145/1869790.1869819
GIS
Keywords
Field
DocType
original edge,input edge,basic property,optimization approach,cartographic quality measure,polygonal ring,new solution,original problem,topologically safe simplification,exact algorithm,efficient algorithm,optimization,integer programming,gis,cartography,map generalization
Integer,Polygon,Mathematical optimization,Exact algorithm,Vertex (geometry),Computer science,Integer programming,Software,Artificial intelligence,Cartographic generalization,Subsequence,Machine learning
Conference
Citations 
PageRank 
References 
7
0.49
8
Authors
2
Name
Order
Citations
PageRank
Jan-Henrik Haunert117919.32
Alexander Wolff222222.66