In computational geometry, the visibility polygon or visibility region for a point in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from . 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 is inside the polygon. In the latter case the visibility polygon may be found in linear time.

Definitions

that is not within an obstacle. Then, the point visibility polygon.

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

, a linear time. 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.

, processing the vertices in the order in which they appear, while maintaining a stack 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

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

algorithm is optimal. This is because a visibility polygon algorithm must output the vertices of the visibility polygon in sorted order, hence the problem of sorting can be reduced to computing a visibility polygon.

Notice that any algorithm that computes a visibility polygon for a point among segments can be used to compute a visibility polygon for all other kinds of polygonal obstacles, since any polygon can be decomposed into segments.

Divide and conquer

A divide-and-conquer algorithm to compute the visibility polygon was proposed in 1987.

Angular sweep

An angular sweep, i.e. rotational plane sweep algorithm to compute the visibility polygon was proposed in 1985 and 1986. The idea is to first sort all the segment endpoints by polar angle, and then iterate over them in that order. During the iteration, the event line is maintained as a heap. An efficient implementation was published in 2014.

Generally intersecting segments

For a point among generally intersecting segments, the visibility polygon problem is reducible, in linear time, to the lower envelope problem. By the Davenport–Schinzel argument is the inverse Ackermann function time was created by John Hershberger in 1989.

References

External links

• http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en (visibility in simple polygons - applets)

Software

• VisiLibity: A free open source C++ library for visibility computations in planar polygonal environments.

• visibility-polygon-js: A public domain Javascript library for computing a visibility polygon for a point among segments using the angular sweep method.