Visibility Region of a Polygon

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

The parts of a polygon reachable by straight lines from a point without hitting a wall are called the visibility region. The visibility region is useful for finding accessible paths. This Demonstration allows you to drag the reference point (or source), shown as a blue disk, to construct a visibility region.

Contributed by: Shreyas Poyrekar, Arifa Sultana and Aaron T. Becker (September 2019)
Open content licensed under CC BY-NC-SA


Details

The visibility region is the set of points in a polygon that are visible from a reference point . Imagine standing at point holding a flashlight in a building whose walls are the polygon. The visibility region is the region illuminated by your flashlight.

To compute the visibility region of a polygon from the point , construct an infinite ray parallel to the axis starting from point . Then find the intersection of all the polygon lines with this infinite ray and add each intersecting line to a list commonly called the list. Sort the list by distance from . The closest line is obviously visible at the intersection point.

Next, sort all the polygon vertices by polar angle from . Then step through each vertex in this loop. For each vertex, construct a ray to the vertex and add the lines that extend in the clockwise half-plane into the list and remove the lines that extend in the counterclockwise half-plane from the list. The vertex is visible only if it is at the top of the list.

The slider in this Demonstration steps through each vertex and shows how the visibility region is constructed.

Calculating the visibility region is necessary for solving the art gallery problem, a canonical computational geometry problem. The visibility region is also often used for robotic motion planning.

References

[1] D.-T. Lee, "Proximity and Reachability in the Plane," Ph.D. dissertation, University of Illinois at Urbana-Champaign, Illinois, ProQuest Dissertations Publishing, 1978 7913526.

[2] Wikipedia. "Visibility Polygon." (Aug 22, 2019) en.wikipedia.org/wiki/Visibility_polygon.

[3] Wikipedia. "Visibility Graph." (Aug 22, 2019) en.wikipedia.org/wiki/Visibility_graph.

[4] Wikipedia. "Art Gallery Problem." (Aug 22, 2019) en.wikipedia.org/wiki/Art_gallery_problem.

[5] Wikipedia. "Isovist." (Aug 22, 2019) en.wikipedia.org/wiki/Isovist.


Snapshots



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send