Visibility Queries of Points in Polygons by Decomposed Convex Segments and Grids

It is a basic operation in computational geometry to detect the visible edges of a point in a polygon.With regard to this,this paper presents a new algorithm for acceleration.Firstly,it decomposes the polygon into convex segments,to take the advantage that it is fast to compute the visible edges of a point in a convex polygon.Then,it uses a grid to treat convex segments from near to far,to avoid treating those occluded ones.Also by the grid,the new algorithm can be easily implemented in parallel.The new algorithm treats the polygons with or without holes uniformly.It has a lower time complexity O(n) on preprocessing to construct a data structure in O(n) storage,while finds visible edges of a point in O(log n)O(n) time adaptively,where n is the number of polygon edges.