For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Algorithm for Finding the Visibility Polygon for a Polygonal Region with Holes
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1985/09/25
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Data Processing
Full Text: PDF(217.9KB)>>
We are given a polygonal region P with holes and one point q is specified in the region. The problem is how fast we can find the portion of the boundary of P that is visible from q. For this problem an efficient algorithm is presented which runs in time O(n log h) in the worst case and in time O(n+h log h) if every hole is a convex polygon, where n is the total number of vertices of P and h is the number of holes.