Maintaining Visibility Polygon of a Moving Point Observer in Polygons with Holes

Computing the visible region from a moving point in planar environments has many applications in computer graphics and computational geometry. This problem has been considered thoroughly be- fore and several algorithms have been proposed for it. Almost all these solutions use a preprocess- ing step to build data structures which re°ect the visibility coherence of the scene. Then, this data is used to facilitate visibility computation for the moving observer. Since combinatorial structure of the observer visible area is changed in discrete points along its motion path, these algorithms main- tain a queue of events which speci¯es these points. Unfortunately, in these algorithms either some un- necessary events are handled or their handling time is not e±cient. In this paper, we present an algo- rithm for this problem which processes only nec- essary events as well as the events are handled ef- ¯ciently. This algorithm uses the method of [1] to preprocess the scene. Although this preprocess- ing step is expensive, it helps to ¯nd and maintain visibility polygon of an arbitrary moving observer more e±ciently. The method of [1] computes visi- bility polygon of a point and here we extend that method for a moving point observer.

کلیدواژه ها:

Computational geometry ، polygon with holes ، visibility polygon ، moving observer