On the correctness of a linear-time visibility polygon algorithm∗
- 1 January 1990
- journal article
- research article
- Published by Taylor & Francis in International Journal of Computer Mathematics
- Vol. 32 (3-4) , 155-172
- https://doi.org/10.1080/00207169008803824
Abstract
We prove the correctness of the linear-time algorithm in Joe and Simpson [7] for computing the visibility polygon of a simple polygon from a viewpoint that is either interior to the polygon or in its blocked exterior. This proof establishes pre- and post-conditions for all steps of the algorithm. The algorithm and the proof are identical for interior and blocked exterior viewpoints. Other algorithms for computing the visibility polygon (usually for interior viewpoints only) are either nonlinear-time and harder to implement or can fail for polygons that wind sufficiently.Keywords
This publication has 9 references indexed in Scilit:
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple PolygonSIAM Journal on Computing, 1988
- Corrections to Lee's visibility polygon algorithmBIT Numerical Mathematics, 1987
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987
- Triangular meshes for regions of complicated shapeInternational Journal for Numerical Methods in Engineering, 1986
- Visibility of a simple polygonComputer Vision, Graphics, and Image Processing, 1983
- A theorem on polygon cutting with applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A linear algorithm for computing the visibility polygon from a pointJournal of Algorithms, 1981
- Decomposition of Polygons into Convex SetsIEEE Transactions on Computers, 1978
- An Algorithm for the Solution of the Two-Dimensional ``Hidden-Line'' ProblemIEEE Transactions on Electronic Computers, 1967