 |
|
|
|
|
Simple means:
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.
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:
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
.
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.
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.
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.
