Maintaining visibility of a polygon with a moving point of view
Danny Z. Chen, Ovidiu Daescu · Information Processing Letters · 1998
The following problem is studied in this paper: Given a scene with an n-vertex simple polygon and a trajectory path in the plane, construct a data structure for reporting the perspective view from a moving point along the trajectory. We present conceptually simple algorithms for the cases of this problem in which the trajectory path consists of several line segments or of a conic curve that contains the polygon. Our algorithms take O(n log n) time and O(n) space. We also prove that the problem of reporting perspective views from successive points along a trajectory path takes n log n) time in the worst case in the algebraic computation tree model. Our data structure reports the view from any query point on the trajectory in O(k + log n) time for a view of size k. Keywords: Algorithms, visibility, simple polygon, trajectory, topology change, shortest path. 1 Introduction In this paper, we study the following problem: Given a scene with an n-vertex simple polygon P and a trajectory ...