In computational geometry, the visibility polygon or visibility region for a point p in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from p. The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in various optimization problems such as the facility location problem and the art gallery problem. If the visibility region is bounded then it is a star-shaped polygon. A visibility polygon is bounded if all rays shooting from the point eventually terminate in some obstacle. This is the case, e.g., if the obstacles are the edges of a simple polygon and p is inside the polygon. In the latter case the visibility polygon may be found in linear time.
Definitions Formally, we can define the planar visibility polygon problem as such. Let S {\displaystyle S} be a set of obstacles (either segments, or polygons) in R 2 {\displaystyle \mathbb {R} ^{2}} . Let p {\displaystyle p} be a point in R 2 {\displaystyle \mathbb {R} ^{2}} that is not within an obstacle. Then, the point visibility polygon V {\displaystyle V} is the set of points in R 2 {\displaystyle \mathbb {R} ^{2}} , such that for every point q {\displaystyle q} in V {\displaystyle V} , the segment p q {\displaystyle pq} does not intersect any obstacle in S {\displaystyle S} . Likewise, the segment visibility polygon or edge visibility polygon is the portion visible to any point along a line segment.
Applications Visibility polygons are useful in robotics. For example, in robot localization, a robot using sensors such as a lidar will detect obstacles that it can see, which is similar to a visibility polygon. They are also useful in video games, with numerous online tutorials explaining simple algorithms for implementing it.
Algorithms for point visibility polygons
Optimal algorithms for a point in a simple polygon
Given a simple polygon P {\displaystyle {\mathcal {P}}} and a point p {\displaystyle p} , a linear time algorithm is optimal for computing the region in P {\displaystyle {\mathcal {P}}} that is visible from p {\displaystyle p} . Such an algorithm was first proposed in 1981. However, it is quite complicated. In 1983, a conceptually simpler algorithm was proposed, which had a minor error that was corrected in 1987. The latter algorithm will be briefly explained here. It simply walks around the boundary of the polygon P {\displaystyle {\mathcal {P}}} , processing the vertices in the order in which they appear, while maintaining a stack of vertices S = s 0 , s 1 , ⋯ , s t {\displaystyle {\mathcal {S}}=s_{0},s_{1},\cdots ,s_{t}} where s t {\displaystyle s_{t}} is the top of the stack. The stack constitutes the vertices encountered so far which are visible to p {\displaystyle p} . If, later during the execution of the algorithm, some new vertices are encountered that obscure part of S {\displaystyle {\mathcal {S}}} , then the obscured vertices in S {\displaystyle {\mathcal {S}}} will be popped from the stack. By the time the algorithm terminates, S {\displaystyle {\mathcal {S}}} will consist of all the visible vertices, i.e. the desired visibility polygon. An efficient implementation was published in 2014.
Optimal algorithms for a point in a polygon with holes For a point in a polygon with h {\displaystyle h} holes and n {\displaystyle n} vertices in total, it can be shown that in the worst case, a Θ ( n + h log h ) {\displaystyle \Theta (n+h\log h)} algorithm is optimal. Such an algorithm was proposed in 1995 together with its proof of optimality. However, it relies on the linear time polygon triangulation algorithm by Chazelle, which is extremely complex.
Optimal algorithms for a point among segments
Segments that do not intersect except at their endpoints
… excerpt ends here. Continue reading the full article.
