Simple traversal of a subdivision without extra storage
Simple traversal of a subdivision without extra storage
复制标题
简单遍历细分，无需额外存储
DOI：
10.1145/237218.237408
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
M. Overmars
中科院分区：
文献类型：
--
作者：
M. D. Berg;M. V. Kreveld;R. V. Oostrum;M. Overmars
在本文中，我们展示了如何遍历细分并报告所有单元、边和顶点，而不使用结构或堆栈中的标记位。我们通过对细分执行深度优先搜索来做到这一点，使用本地标准来决定下一个要访问的单元格是什么。我们的方法非常简单并且被证明是正确的。该算法在地理信息系统（GIS）领域有应用，其中遍历细分是常见操作，但修改数据库是不需要或不可能的。我们展示了如何调整我们的算法来回答相关查询，例如窗口查询和报告具有共同属性的连接的单元子集。最后，我们展示了如何扩展我们的算法，使其可以处理凸三维细分。
In this paper we show how to traverse a subdivision and to report all cells, edges and vertices, without making use of mark bits in the structure or a stack. We do this by performing a depth-first search on the subdivision, using local criteria for deciding what is the next cell to visit. Our method is extremely simple and provably correct. The algorithm has applications in the field of geographic information systems (GIS), where traversing subdivisions is a common operation, but modifying the database is unwanted or impossible. We show how to adapt our algorithm to answer related queries, such as windowing queries and reporting connected subsets of cells that have a common attribute. Finally, we show how to extend our algorithm such that it can handle convex threedimensional subdivisions.