Simulate the rotational sweep algorithm for finding the visible vertices for the given set of polygons.

The exercise uses the following visualizations. On the left there is an area which shows the point being examined, the rotational sweep line, and the polygons. Topmost on the right are the current vertex being examined and the next vertex. Below them is the list of visible vertices. Underneath these is the status structure used to find out whether a vertex is visible or not. The status structure used is a red-black tree.

The polygon endpoints have already been ordered (as per code line 3). You can move to the next vertex by pushing the rotate-button.

Polygon edges can be added to the status structure by dragging them from the area visualization and dropping them over the status structure visualization. The edges should be dropped over the structure header. Edges can be deleted from the status structure by dragging them from the status structure visualization.

A point can be added to the list of visible points by dragging it from the current vertex visualization or from the area visualization.

The visibility test (pseudocode line 8) can be done by selecting a node from the status structure. The node is selected by clicking it with the mouse. A selected node is highlighted in green. No selection needs to be done if the structure is empty.

If you have problems solving the exercises, contact the course staff.

VISIBLE_VERTICES(PolygonSet S, Point p)
 1. initialize balanced search tree T
 2. initialize list L
 3. Sort the obstacle vertices in set S according to the 
    clockwise angle that the half-line from p to each vertex 
    makes with the positive x-axis. In case of ties vertices 
    closer to p should come before vertices farther from p. Let 
    W1, ..., Wn be the sorted list.
 4. Let r be the half-line parallel to the positive x-axis 
    starting at p. Find the obstacle edges that are properly 
    intersected by r, and store them in a balanced search tree
    T in the order in which they are intersected by r.
 5. i = 1 // rotate the ray to the first vertex
 6. while not (i > n)
 7.   Delete from T the obstacle edges incident to Wi that lie 
      on the counterclockwise side of the half-line from p to 
      Wi.
 8.   if (VISIBLE(p, Wi, T))
 9.     L.append(Wi)
10.   Insert into T the obstacle edges incident to Wi that lie 
      on the clockwise side of the half-line from p to Wi.
11.   increment i // rotate the ray to the next vertex
12. return L
VISIBLE(Point p, Point Wi, Tree T)
1. Let line l be a line from p to Wi.
2. Search in T for the edge e nearest to p.
3. If e exists and e intersects l
4.   return false
5. else
6.   return true