Area-Preserving Simplification and Schematization of Polygonal Subdivisions
Kevin Buchin, Wouter Meulemans, André van Renssen, Bettina Speckmann · ACM Transactions on Spatial Algorithms and Systems · 2016
In this article, we study automated simplification and schematization of territorial outlines. We present a quadratic-time simplification algorithm based on an operation called edge-move . We prove that the number of edges of any nonconvex simple polygon can be reduced with this operation. Moreover, edge-moves preserve area and topology and do not introduce new orientations. The latter property in particular makes the algorithm highly suitable for schematization in which all resulting lines are required to be parallel to one of a given set of lines (orientations). To obtain such a result, we need only to preprocess the input to use only lines that are parallel to one of the given set. We present an algorithm to enforce such orientation restrictions, again without changing area or topology. Experiments show that our algorithms obtain results of high visual quality.