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