Translator Disclaimer
1 December 1993 Computing stair-case visibility polygon
Author Affiliations +
Proceedings Volume 2060, Vision Geometry II; (1993)
Event: Optical Tools for Manufacturing and Advanced Automation, 1993, Boston, MA, United States
Given a point q in the presence of polygonal obstacles, the set of points visible from q is the visibility polygon from q. We consider the problem of computing visibility polygon under stair-case visibility (s-visibility, in short). We show that the s-visibility polygon from a point inside a simple orthogonal polygon of n sides can be computed in O(n) time. When the polygon contains holes the algorithm runs in O(n log n) time, which we prove to be optimal by linear time reduction from sorting. We also consider the problem of recognizing stair-case star polygons (s-star, in short) and present an algorithm which recognizes simple s-star polygons in O(n) time.
© (1993) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Laxmi P. Gewali "Computing stair-case visibility polygon", Proc. SPIE 2060, Vision Geometry II, (1 December 1993);

Back to Top