Hide text Hide pseudo-code | |

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 |