## Visibility in simple polygons

Two applets are presented here:- Kernel of a polygon
- Visibility polygon of a polygon

### How to use the applets

Both applets contain an editor for constructing a*simple*polygon.

*Simple* means:

- The polygon must have at least 3 points.
- Two edges' only common point is one of these polygon points.
- The polygon is
*closed*. (The polygon has*n*pointsand edges.)

At the moment when a

*simple*polygon is closed, all other single points and segments - if any - disappear and only the simple polygon remains.

The *kernel* / the *visibility polygon* is then drawed into the
closed polygon.

After the polygon is closed, it's shape can be changed further; the editor
allows not only moving of points, edges, or the whole polygon, but also rotating,
scaling and shearing the polygon, by choosing an option in a context menu
which opens upon a click on the polygon with the right mouse button.

Points and edges can also be removed and new ones can be added to the polygon.

Every change of the polygon's shape - if closed - is immediately followed
by a repaint of the whole applet, so changes of the kernel / the visibility
polygon are immediately made visible.

Calculation of a polygon's kernel

This applet shows the *kernel*of a polygon.

The *kernel* of a polygon is defined by the set of points from within
the polygon from which the whole polygon is visible.

In formula:

*ker*(

*P*) = {

*p*element

*P*;

*vis*(

*p*)=

*P*}.

The kernel has - if existent - a polygon's shape. In other word, the kernel
is just the polygon's region from which one can have a "look in all corners".

* Closed* polygon is painted in **grey**
.

*Kernel* of polygon is painted in **green**
.

**Algorithm and running time**

In short, the algorithm calculates the kernel as intersection
of half planes *H*^{+}(*k*), where *H*^{+}
(*k*) is the half plane to the left of egde *k* that contains the
inside of the polygon; intersection is calculable in *O*(*n*).
Thereby the lines which define the half planes are ascertained and sorted
by angle, which is likewise feasible in *O*(*n*). The result is:

**Theorem** A simple polygon's kernel with *
n* vertices can be calculated in time *O*(*n*) and linear memory
space.

Calculation of a polygon's visibility
polygon

This applet shows the *visibility polygon*of a polygon, visible from a

*base point*.

The *visibility polygon vis*(*p*) of a polygon *P* is defined
by the set of all points that are visible from the *base point p*.

This set has by definition a polygon's shape. In other words, one can compare
the visibility polygon to the light that a light source standing at the base
point throws around; the visibility polygon then represents the polygonal room's
area which is hit by the light.

*Closed* polygon is painted in **grey**
.

*Visibility polygon* is shown in **yellow**
.

*Base point *of visibility polygon is drawn in **
red**.

**Algorithm and running time**

This algorithm proceeds as follows:

First, a vertex *R _{0}*, that is visible from the base point

*p*in any case, is ascertained.

Then, the boundary is searched counterclockwisely, and all boundary parts that are visible from

*p*are determined.

After the initial starting point

*R*is reached again, the visibility polygon is constructed from these boundary parts and additional constructed straight lines that connect these parts.

_{0}**Theorem**The visibility polygon of point

*p*in a simple polygon

*P*can be calculated in linear time and in linear memory space.

It's easy to see why this algorithm manages with linear time: The polygon's
boundary is searched only once, und determination of starting point *R _{
0}* is also feasible in linear time.