A Unified Approach to Conic Visibility
A Unified Approach to Conic Visibility
复制标题
DOI：
10.1007/s004530010042
复制
发表时间：
2000-11
期刊：
影响因子：
1.1
通讯作者：
J. García-López;P. Ramos
中科院分区：
文献类型：
--
作者：
J. García-López;P. Ramos
在本文中，我们提出了一种线性时间算法，用于计算从一个点开始的最短路径树和三角形曲线多边形内弧的弱可见多边形。我们还提出了一种线性时间算法，用于计算从固定弧发出的射线集的平面细分（在参数空间中），使得细分的每个面对应于击中多边形相同弧的射线。虽然这些结果涉及到对直线多边形已知结果的非平凡推广，可能对其本身有一些兴趣，但本文的主要结果是一个线性时间算法，用于计算简单多边形内一点的圆锥（圆形、椭圆形、抛物线和双曲）可见性多边形。我们的技术相对于之前的圆形可见性结果的主要优势在于，它提供了一个简单、统一的圆锥可见性方法。最后，我们提出了一种线性时间算法，用于在参数空间中计算从固定点发出的双参数族圆锥射线的平面细分，使得细分的每个面对应于击中多边形同一边缘的圆锥射线。所有这些算法都是渐近最优的。
{In this paper we present linear time algorithms for computing the shortest path tree from a point and the weak visibility polygon of an arc inside a triangulated curved polygon. We also present a linear time algorithm for computing the planar subdivision (in the parametric space) of the set of rays emanating from a fixed arc, such that each face of the subdivision corresponds to rays hitting the same arc of the polygon. Although these results, which involve nontrivial generalizations of known results for rectilinear polygons, may have some interest in its own right, the main result of this paper is a linear time algorithm for computing the conic (circular, elliptic, parabolic, and hyperbolic) visibility polygon of a point inside a simple polygon. The main advantage of our technique over previous results on circular visibility is that it provides a simple, unified approach to conic visibility. Finally, we present a linear time algorithm for computing the planar subdivision, in the parametric space, of two-parametric families of conic rays emanating from a fixed point, such that each face of the subdivision corresponds to conic rays hitting the same edge of the polygon. All these algorithms are asymptotically optimal.}