Below is a visibility polygon demo written in Processing
and running in Javascript. The source code is
available on github here.
Usage Instructions:
- Create a polygon in the grey space below by left-clicking to add vertices one-by-one.
- Close off the polygon by clicking on the initial vertex placed.
- Place a point inside the polygon somewhere.
- The point can now be re-placed or moved using your arrow keys.
Note that the line intersection computation currently does not handle small angles / non-general-position
cases very well yet. As a result when the guard is on or near the line of sight of a reflex vertex
in the polygon the visibility windows may not be computed correctly.
When moving your point inside the polygon with the arrow keys, the visibility polygon (VP)
changes very little. As such, we need only recompute the portions of the VP
which change. The transition from one VP to another can be computed by a dynamic
VP algorithm. We discuss a possible dynamic VP algorithm here.
The assumptions made in this algorithm are:
- The polygon is unchanging
- Precomputation time abundant.
- Memory is abundant.
- The point inside the polygon makes "very small" movements.