Corrections to Lee's visibility polygon algorithm |
| |
Authors: | B. Joe R. B. Simpson |
| |
Affiliation: | (1) Dept. of Computing Science, University of Alberta, T6G 2H1 Edmonton, Alberta, Canada;(2) Dept. of Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
Abstract: | We present a modification and extension of the (linear time) visibility polygon algorithm of Lee. The algorithm computes the visibility polygon of a simple polygon from a viewpoint that is either interior to the polygon, or in its blocked exterior (the cases of viewpoints on the boundary or in the free exterior being simple extensions of the interior case). We show by example that the original algorithm by Lee, and a more complex algorithm by El Gindy and Avis, can fail for polygons that wind sufficiently. We present a second version of the algorithm, which does not extend to the blocked exterior case.This work was partially supported by grants from the Central Research Fund of the University of Alberta and the Natural Sciences and Engineering Research Council of Canada. |
| |
Keywords: | F.2.2 |
本文献已被 SpringerLink 等数据库收录! |
|