Visibility polygon

Visibility polygon vis (p) in red of a polygon

The visibility ${\displaystyle vis(p)}$polygon of a point is an object of and is that part of the interior of a simple polygon that is visible from the point . ${\displaystyle p}$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle P}$ ${\displaystyle p}$

It is used, for example, in path finding algorithms in robotics .

Algorithm for determination

To determine , an arbitrarily chosen point on ( edge of the polygon ) is determined first, which is definitely visible from. This is possible during the term . Now it runs counterclockwise from out . The already visited pieces of the , which are possibly visible from here, are stored in a stack memory . ${\displaystyle vis(p)}$ ${\displaystyle R_{0}}$ ${\displaystyle \partial P}$ ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle R_{0}}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle \partial P}$ ${\displaystyle p}$

When the scan comes back to , S contains exactly those parts of which are visible from . Now artificial edges have to be inserted so that the visibility polygon is closed. ${\displaystyle R_{0}}$ ${\displaystyle p}$ ${\displaystyle \partial P}$ ${\displaystyle S}$

This algorithm determines the visibility polygon with linear runtime and linear storage space . ${\displaystyle {\mathcal {O}}(n)}$ ${\displaystyle {\mathcal {O}}(n)}$

See also

• Visibility problem

literature

• Rolf Klein: Construction of the Visibility Polygon in Algorithmic Geometry. Springer Verlag Berlin Heidelberg Munich 2005, ISBN 3540209565 , pp. 182-184.

Web links

• Calculation of the visibility polygon - Interactive Java applet