Visibility Queries and Maintenance in Simple Polygons
Visibility Queries and Maintenance in Simple Polygons
复制标题
DOI：
10.1007/s00454-001-0089-9
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
B. Aronov;L. Guibas;M. Teichmann;Li Zhang
中科院分区：
文献类型：
--
作者：
B. Aronov;L. Guibas;M. Teichmann;Li Zhang
在这篇文章中，我们探索了简单多边形P内固定点和移动点的可见性的一些新方面。我们提供了一种机制，用于将一个点的可见性多边形表示为使用二次空间数据结构的对数多个标准块的不相交并。这使我们能够在时间上报告与其大小成比例的可见性多边形，但不需要以前方法的立方体空间开销。相同的规范分解可用于确定锥体内的可见性，或有效地计算可见性多边形的各种属性。通过探索可见性多边形和最短路径树之间的联系，我们得到了一个动态算法，该算法可以跟踪视点在P内沿多边形路径移动时的可见性多边形，并且每次可见性或点的飞行计划的组合变化的代价是多对数的。静态算法和动态算法的结合导致了一种新的静态算法，在该算法中，我们可以用增加的查询时间来换取更多的空间。作为另一个应用，我们得到了一个在输出敏感时间内从查询片段计算弱可见性多边形的算法。
In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygonP. We provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This allows us to report visibility polygons in time proportional to their size, but without the cubic space overhead of earlier methods. The same canonical decomposition can be used to determine visibility within a frustum, or to compute various attributes of the visibility polygon efficiently. By exploring the connection between visibility polygons and shortest-path trees, we obtain a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths insideP, at a polylogarithmic cost per combinatorial change in the visibility or in the flight plan of the point. The combination of the static and kinetic algorithms leads to a new static algorithm in which we can trade off space for increased overhead in the query time. As another application, we obtain an algorithm which computes the weak visibility polygon from a query segment insidePin output-sensitive time.