## Line Sweep

 Hide textShow text Hide pseudo-codeShow 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) ``` ```FIRST_POINT(P) 1. let S be the line segment corresponding to P 2. add S to A 3. let R and T be neighbours of S in A 4. if R and S intersect add intersection to Q 5. if T and S intersect add intersection to Q ``` ```SECOND_POINT(P) 1. let S be the line segment corresponding to P 2. let R and T be neighbours of S in A 3. remove S from A 4. if R and T intersect in point P' AND P.y > P'.y AND P' has not been discovered before 5. add P' to Q ``` ```INTERSECTION(P) 1. let S and T be the intersecting lines 2. swap positions of S and T in A 3. let R be the new neighbour of T in A let U be the new neighbour of S in A 4. if R and T intersect at point P' AND P.y > P'.y AND P' has not been discovered before 5. add P' to Q 6. if S and U intersect at point P' AND P.y > P'.y AND P' has not been discovered before 7. add P' to Q 8. Add P to output ```