TRAKLA2 - Line Sweep

Line Sweep

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Simulate the line sweep algorithm for finding line segment intersections. You must manage the event queue and neighbour structures. Line sweep is a common approach in solving different problems algorithmically. It is used a space is searched for something, eg. intersection points of lines or polygons or closest pair of points in a set. It can be used in thinning algorithms, map overlay, label placement algorithms etc. The basic idea is to imagine a line that sweeps over the area and handles the objects when they are encountered. This reduces the amount of events that are needed to handle. Currently handled points are kept in a neighbour structure. In this implementation of line sweep the sweep line moves according to the y-axis. Therefore, the events points (line segment endpoints and intersection points) are kept in an priority queue according to their y-coordinate (if two points have the same y-coordinate the one with smaller x-coordinate has higher priority). The priority queue used in this exercise is a binary heap. The neighbour structure tells which line segments are next to each other in the current line sweep position. The line segments are arranged in the neighbour structure according to the x-coordinate of the point where they intersect the sweep line. In this exercise the neighbour structure is shown as an array. Typical implementations will use, for example, balanced binary trees for storing the neighbour relations. Intersection points discovered are shown in the line segment view. The intersections will appear in the window when the algorithm discovers them (when the two intersecting line segments are neighbours in the neighbour structure). Intersections can be inserted to the priority queue by dragging them from the line segment view to the header of priority queue. Elements can be dragged from the priority queue to the neighbour structure. A new element can be added to the structure by dropping it over the desired index. The other elements in the table will be adjusted to make room for the new structure. Elements already in the structure can be swapped by dropping one element on top of the other. Elements can be deleted from the neighbour structure by dragging from the structure. Elements can be dragged from the priority queue to the output. New element can be added to the output by dropping it on the output header.
main FIRST_POINT SECOND_POINT INTERSECTION 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 Q 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