Area-Preserving Simplification and Schematization of Polygonal Subdivisions
ACM Transactions on Spatial Algorithms and Systems · 2016
DOI: 10.1145/2818373 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Spatial Algorithms and Systems, 2016. Verfasst von Kevin Buchin und 3 weiteren Autor:innen. Die Arbeit wurde bisher 32-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: Netherlands Organisation for Scientific Research, NSERC and Carleton University’s President’s 2010 Doctoral Fellowship, JST, ERATO, Kawarabayashi Large Graph Project.
Abstract (Originalsprache)
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.
Förderung
- Netherlands Organisation for Scientific Research
- NSERC and Carleton University’s President’s 2010 Doctoral Fellowship
- JST, ERATO, Kawarabayashi Large Graph Project
- EU Horizon 2020 programme, under a Marie Skłodowska-Curie Individual Fellowship
Zitieren
APA
Buchin, K., Meulemans, W., Renssen, A. V., & Speckmann, B. (2016). Area-Preserving Simplification and Schematization of Polygonal Subdivisions. ACM Transactions on Spatial Algorithms and Systems. https://doi.org/10.1145/2818373
Vancouver
Buchin K, Meulemans W, Renssen AV, Speckmann B. Area-Preserving Simplification and Schematization of Polygonal Subdivisions. ACM Transactions on Spatial Algorithms and Systems. 2016. doi:10.1145/2818373
BibTeX
@article{Buchin2016,
author = {Buchin, Kevin and Meulemans, Wouter and Renssen, André Van and Speckmann, Bettina},
title = {Area-Preserving Simplification and Schematization of Polygonal Subdivisions},
journal = {ACM Transactions on Spatial Algorithms and Systems},
year = {2016},
doi = {10.1145/2818373}
}
EUVIMED