| 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
|