Computing stair-case visibility polygon

Laxmi P. Gewali

doi:10.1117/12.164994

1 December 1993 Computing stair-case visibility polygon

Laxmi P. Gewali

Proceedings Volume 2060, Vision Geometry II; (1993) https://doi.org/10.1117/12.164994
Event: Optical Tools for Manufacturing and Advanced Automation, 1993, Boston, MA, United States

Abstract

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.

Citation Download Citation

Laxmi P. Gewali "Computing stair-case visibility polygon", Proc. SPIE 2060, Vision Geometry II, (1 December 1993); https://doi.org/10.1117/12.164994

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available