One of the questions on the final exam of the Geometric Algorithms course on the Utrecht University caught my eye. The question was to come up with a sweep line algorithm to find all the segments S that are visible from a point P in Ο(n log n) time by using a sweep line algorithm.

In this demo a visibility polygon can be created in a 2-dimensional space, the plane. The region of the visibility polygon equals all the points in the plane to which a line can be drawn from the view point that doesn't intersect any wall. The visibility polygon is computed in Ο(n log n) time, in which n is linear to the number of walls in the scene.

Live Demo

Click with the mouse in the plane to add new walls to the scene. Hold <control> while moving the mouse to change the view point.