Area-Preserving Simplification and Schematization of Polygonal Subdivisions
Area-Preserving Simplification and Schematization of Polygonal Subdivisions
复制标题
DOI：
10.1145/2818373
复制
发表时间：
2016-01-01
影响因子：
1.9
通讯作者：
Speckmann, Bettina
中科院分区：
文献类型：
--
作者：
Buchin, Kevin;Meulemans, Wouter;Speckmann, Bettina
在这篇文章中，我们研究自动简化和图式化的领土轮廓。我们提出了一个二次时间简化算法的基础上的操作称为边移动。我们证明了任何非凸简单多边形的边数都可以用这种运算来减少。此外，边移动保持面积和拓扑结构，并且不引入新的方向。特别是后者的属性使得算法非常适合于图式化，其中所有产生的线都需要平行于一组给定的线（方向）。为了获得这样的结果，我们只需要对输入进行预处理，只使用与给定集合之一平行的直线。我们提出了一个算法来执行这样的方向限制，再次不改变面积或拓扑结构。实验结果表明，我们的算法获得了较高的视觉质量的结果。
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.