This paper presents an optimization approach to simplify building ground plans given by two-dimensional polygons. We define a simplified building as a subsequence of the original building edges; its vertices are defined by intersections of consecutive (and possibly extended) edges in the selected sequence. Our aim is to minimize the number of edges subject to a user-defined error tolerance. We prove that this problem is NP-hard when requiring that the output consists of non-intersecting simple polygons. Thus we cannot hope for an efficient, exact algorithm. Instead, we propose a heuristic and an integer programming formulation that can be used to solve the problem with existing optimization software. We discuss results of our algorithms and how to incorporate more sophisticated objective functions into our model.
|Name||The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences|