| Hide text Hide pseudo-code | |
|
Important notice! The automatic assessment does not always seem to work correctly with this exercise. If the assessment gives you odd feedback (e.g. no points when you think you should gain some) contact the course staff. Especially if the feedback reads "0 points out of 0 correct" contact the course staff. Simulate the rotational sweep algorithm for finding the visible vertices for the given set of polygons. |
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
|