An Algorithm for Visibility Computation of Points in Polygon

Visibility computation is a fundamental problem in computational geometry.This paper presents a Voronoi diagram-based algorithm for computing the visibility polygon of any point in the polygon.First,the definitions of Voronoi corridors and local shortest paths in Voronoi corridors are proposed.Then the depth-first search for traversing the Voronoi diagram is performed to compute Voronoi skeleton paths and the local shortest paths from a point to the vertices of the polygon.Afterwards,the visibility portions of the polygon edges are computed.Compared with the popular visibility algorithms based on triangulation,the proposed algorithm can deal with the polygon with holes and partially visiting the polygon only.Compared with algorithms based on visual cell subdivision or visible graphs,the proposed algorithm has a simpler data structure,more reasonable space subdivision,easier implementation,and only takes O(n) space and O(n lg n) preprocessing time.Examples show that the algorithm is of practical effectiveness,and the running time is approximately linear to the number of the edges of the visibility polygon of a point and the number of the edges of the polygon.