{{Short description|Polygonal region of all points visible from a given point in a plane}} thumb|right|Visibility polygon shown in yellow. Four obstacles are shown in blue.
In computational geometry, the '''visibility polygon''' or '''visibility region''' for a point {{mvar|p}} in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from {{mvar|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 {{mvar|p}} is inside the polygon. In the latter case the visibility polygon may be found in linear time.<ref name=PS>{{cite book |author = Franco P. Preparata and Michael Ian Shamos | title = Computational Geometry - An Introduction | publisher = Springer-Verlag| year = 1985 | isbn = 0-387-96131-3 | id = 1st edition; 2nd printing, corrected and expanded, 1988: {{ISBN|3-540-96131-3}}; Russian translation, 1989: {{ISBN|5-03-001041-6}}}}</ref><ref name=ea>{{cite journal | last1 = El Gindy | first1 = Hossam | last2 = Avis | first2 = David | title = A linear algorithm for computing the visibility polygon from a point | journal = Journal of Algorithms | volume = 2 | issue = 2 | year = 1981 | pages = 186–197 | doi = 10.1016/0196-6774(81)90019-5 }}</ref><ref name=lee>{{cite journal | last = Lee | first = D. T. | title = Visibility of a simple polygon | journal = Computer Vision, Graphics, and Image Processing | volume = 22 | issue = 2 |date=May 1983
| pages = 207–221 | doi = 10.1016/0734-189X(83)90065-8 }}</ref><ref name=js>{{cite journal | last1 = Joe | first1 = Barry | last2 = Simpson | first2 = R. B. | title = Corrections to Lee's visibility polygon algorithm | journal = BIT Numerical Mathematics | volume = 27 | issue = 4 | year = 1987 | pages = 458–473 | doi = 10.1007/BF01937271 | s2cid = 19112466 }}</ref>
== Definitions == Formally, we can define the planar visibility polygon problem as such. Let <math>S</math> be a set of obstacles (either segments, or polygons) in <math>\mathbb{R}^2</math>. Let <math>p</math> be a point in <math>\mathbb{R}^2</math> that is not within an obstacle. Then, the ''point visibility polygon'' <math>V</math> is the set of points in <math>\mathbb{R}^2</math>, such that for every point <math>q</math> in <math>V</math>, the segment <math>pq</math> does not intersect any obstacle in <math>S</math>.
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.<ref name="guibas">{{cite conference | last1 = Guibas | first1 = Leonidas | last2 = Motwani | first2 = Rajeev | last3 = Raghavan | first3 = Prabhakar | title = The robot localization problem in two dimensions | year = 1992 | conference = ACM-SIAM symposium on Discrete algorithms | publisher = Society for Industrial and Applied Mathematics }}</ref>
They are also useful in video games, with numerous online tutorials explaining simple algorithms for implementing it.<ref name="ncase">{{cite web | url = http://ncase.me/sight-and-light/ | title = SIGHT & LIGHT how to create 2D visibility/shadow effects for your game | last = Liow | first = Nicklaus | access-date = 9 May 2014 }}</ref><ref name="redblob">{{cite web | url = http://www.redblobgames.com/articles/visibility/ | title = 2d Visibility Algorithm | last = Patel | first = Amit | access-date = 9 May 2014 | date = 5 July 2012 }}</ref>
== Algorithms for point visibility polygons == === Optimal algorithms for a point in a simple polygon === thumb|A visibility polygon for a point in the center (shown in white) inside a simple polygon, outlined in black. Given a simple polygon <math>\mathcal{P}</math> and a point <math>p</math>, a linear time algorithm is optimal for computing the region in <math>\mathcal{P}</math> that is visible from <math>p</math>. Such an algorithm was first proposed in 1981.<ref name="ea"/> However, it is quite complicated. In 1983, a conceptually simpler algorithm was proposed,<ref name="lee"/> which had a minor error that was corrected in 1987.<ref name="js"/>
The latter algorithm will be briefly explained here. It simply walks around the boundary of the polygon <math>\mathcal{P}</math>, processing the vertices in the order in which they appear, while maintaining a stack of vertices <math>\mathcal{S}=s_0, s_1,\cdots, s_t</math> where <math>s_t</math> is the top of the stack. The stack constitutes the vertices encountered so far which are visible to <math>p</math>. If, later during the execution of the algorithm, some new vertices are encountered that obscure part of <math>\mathcal{S}</math>, then the obscured vertices in <math>\mathcal{S}</math> will be popped from the stack. By the time the algorithm terminates, <math>\mathcal{S}</math> will consist of all the visible vertices, i.e. the desired visibility polygon. An efficient implementation was published in 2014.<ref name="bungiu" />
=== Optimal algorithms for a point in a polygon with holes === For a point in a polygon with <math>h</math> holes and <math>n</math> vertices in total, it can be shown that in the worst case, a <math>\Theta(n + h\log h)</math> algorithm is optimal. Such an algorithm was proposed in 1995 together with its proof of optimality.<ref name="hlogh">{{cite journal | last1 = Heffernan | first1 = Paul | last2 = Mitchell | first2 = Joseph | title = An optimal algorithm for computing visibility in the plane | journal = SIAM Journal on Computing | volume = 24 | issue = 1 | pages = 184–201 | year = 1995 | doi = 10.1137/S0097539791221505 | url = https://ecommons.cornell.edu/bitstream/1813/8838/1/TR000953.pdf | hdl = 1813/8838 | hdl-access = free }}</ref> 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 ==== thumb|A visibility polygon for a point in the center (shown in white) amongst a set of arbitrary line segments in the plane, allowed to intersect only at their endpoints, acting as obstacles (shown in black). For a point among a set of <math>n</math> segments that do not intersect except at their endpoints, it can be shown that in the worst case, a <math>\Theta(n\log n)</math> 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.<ref name="so">{{cite conference | last1 = Suri | first1 = Subhash | last2 = O'Rourke | first2 = Joseph | title = Worst-case optimal algorithms for constructing visibility polygons with holes | conference = Symposium on Computational geometry | publisher = ACM | year = 1986 | pages = 14–23 | doi = 10.1145/10515.10517 }}</ref>
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.<ref name="am">{{cite tech report | last1 = Arkin | first1 = E. | author1-link = Esther Arkin | last2 = Mitchell | first2 = Joseph | author2-link = Joseph S. B. Mitchell | title = An optimal visibility algorithm for a simple polygon with star-shaped holes | institution = Cornell University Operations Research and Industrial Engineering | year = 1987 | number = 746 }}</ref>
===== Angular sweep ===== An ''angular sweep'', i.e. rotational plane sweep algorithm to compute the visibility polygon was proposed in 1985<ref name="asano">{{cite conference | last = Asano | first = Tetsuo | title = An efficient algorithm for finding the visibility polygon for a polygonal region with holes. | conference = Institute of Electronics, Information, and Communication Engineers | volume = 68 | number = 9 | pages = 557–559 | year = 1985 }}</ref> and 1986.<ref name="so" /> 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.<ref name="bungiu">{{cite arXiv | last1 = Bungiu | first1 = Francisc | last2 = Hemmer | first2 = Michael | last3 = Hershberger | first3 = John | last4 = Huang | first4 = Kan | last5 = Kröller | first5 = Alexander | title = Efficient Computation of Visibility Polygons | eprint = 1403.3905 | date = 2014 | class = cs.CG }}</ref>
==== 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, the lower envelope in the worst case has <math>\Theta(n\alpha(n))</math> number of vertices, where <math>\alpha(n)</math> is the inverse Ackermann function. A worst case optimal divide-and-conquer algorithm running in <math>\Theta(n\log n)</math> time was created by John Hershberger in 1989.<ref name="hershberger">{{cite journal | last = Hershberger | first = John | title = Finding the upper envelope of <math>n</math> line segments in <math>O(n\log n)</math> time | journal = Information Processing Letters | volume = 33 | number = 4 | year = 1989 | pages = 169–174 | doi=10.1016/0020-0190(89)90136-1 }}</ref>
==References== <references/>
== External links == * http://web.informatik.uni-bonn.de/I/GeomLab/VisPolygon/index.html.en (visibility in simple polygons - applets)
===Software=== *[http://www.VisiLibity.org VisiLibity]: A free open source C++ library for visibility computations in planar polygonal environments. *[https://github.com/byronknoll/visibility-polygon-js visibility-polygon-js]: A public domain Javascript library for computing a visibility polygon for a point among segments using the angular sweep method.
Category:Polygons Category:Geometric algorithms