Line Sweep

Hide text Hide pseudo-code

Simulate the line sweep algorithm for finding line segment intersections. You must manage the event queue and neighbour structures.

MAIN()
1. Let Q be a priority queue
2. Let A be an adjacency structure
3. Add all segment endpoints to Q

4. while Q is not empty
5.   let P be a point
6.   remove first element from Q 
     and store it to P
7.   let S be the line segment 
     corresponding to P
8.   if P is first endpoint of S
9.     FIRST_POINT(P)
10.  else if P is second endpoint of S
11.    SECOND_POINT(P)
12.  else if P is and intersection point
13.    INTERSECTION(P)


  Created Wed Jun 20 16:00:44 EEST 2007 - Powered by SVG-hut