Geometry Lab [German] [Sitemap] [About geometrylab.de]

Visibility in simple polygons

Two applets are presented here:

How to use the applets

Both applets contain an editor for constructing a simple polygon.

Simple means:

In the editor the polygon can be constructed of any number of single points and edges/segments.

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 Pvis(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".

(Applet cannot be started)

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.

(Applet cannot be started)

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 R0, 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 R0 is reached again, the visibility polygon is constructed from these boundary parts and additional constructed straight lines that connect these parts.
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.



Bibliography

Rolf Klein. Algorithmische Geometrie, Chapter 4: Durchschnitte und Sichtbarkeit. Addison-Wesley, Bonn, 1997.

 

© University of Bonn, Computer Science I - - Last modified 09-02-2009 10:23