سال انتشار: ۱۳۸۵
محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران
تعداد صفحات: ۷
Alireza Zarei – Computer Engineering Department, sharif University of Technology , Tehran, Iran
Mohammad Ghodsi – Institute for Studies in Teoretical Physics and Mathematics (IPM), Tehran, Iran
In this paper, we are concerned with computing and maintaining the exact visibility polygon V(q) of a moving point observer q in planar scenes represented by a polygon with holes with complexity of n. we propose an algorithm that applies and computes each change to V (q) in constant time as q moves to a new neighboring position. In fact, in our method changes to V (q), as the observer q moves , are applied in linear time in terms of the number of required changes, which is normally algorithm maintains V (q) as a sequence of polygon edges seen by q, and changes to V(q) is computed in O (log(V|(q)|). But in these methods, the computations of exact visibility, needed by the practical applications, requires another trace of V(q). we use a representation of the visibility graph from which the visible area of an observer is updated by merely applying thenecessary changes to the visible area as the observer moves. This is done in optimal time and space without maintaining a queue of future events as previous algorithm do.