Now, our goal is to develop an algorithm for filing line segment intersections, which would not suffer from the drawbacks we have mentioned for the naive algorithm. The overall approach we are going to make use of, is this time a one specific for the area of computation geometry. This is a so-called plane sweep. The general scheme of the planes we approach in the following. We sweep the plane with imaginary line, which is typically horizontal or vertical. Throughout the process, we maintain certain information somehow related to the current position of the sweep line. This information is typically referred to as the sweep line status. The same term is usually applied to the data structure that stores this very information. The status is updated at certain points of interests, which are called the event points. Finally, having performed the entire sweep and also certain actions at the event points, we will come up with getting a solution for our problem. Let us now apply this general scheme to the problem of finding line segment intersections. In parallel illustrated with the process on a simple sample sets consisting of three segments you now see in this slide. The segments are labeled with S_1, S_2, and S_3 respectively. We will sweep the plane with the horizontal line downwards. The status of the sweep line will represent a subset of segments from S, intersected by the sweep line at its current position. Those segments will be ordered by the increasing X coordinate of the intersection point. Initially, the sweep line is at the infinity, and thus it intersects no segments from S. So, the status of the sweep line is an empty set. Later on, it will of course reach our segments set. For the position of the sweep line shown in this slide, the status will comprise the segments S_1 and S_2, resulted the two segments intersected by this line earlier. Then, it will proceed further, and at the moment you see at this slide, the sweep line will intersect three segments, S_1, S_2, and S_3. They will comply the status of this given line L at this moment. After the sweeping line passes over the next event point, which is the intersection point of segments S_1 and S_2, the segments S_1 and S_2 will change their order in the status. Now, we're going to formalize the notion of the event point. In the code of our problem, there will be two types of the event points, and namely segment endpoints shown blue in the slide and intersection points shown red in this slide. It is easy to see that the segment endpoints represent event points. Indeed, at an upper end point of a segment S from our set, a new segment will appear in the status. At the event point, which is the lower end point of sub-segment from our set. This segment will be eliminated from the status. Let us consider an example. For the position of the stripping line you see in the left hand of the slide, two segments from our set are intersected, and namely S_1 and S_2. This is right before the sweep line reaches the upper endpoint of the segment S_3. As soon as this happens, the segment S_3 will be included in the status. Then, the status which now contains the segments S_1, S_3, and S_2 in this very order, will remain the same until the sweep line reach the next event point. Furthermore, let us consider another situation when the sweep line L is about to reach the lower end point of one of the segments from our set, and namely S_2. Right before this happens, there are two segments in this status, S_2 and S_1. After the sweep line reaches the lower endpoint of the segment S_2, the letter will be eliminated from the status, which will now consist of a single segment S_1. Of course, all the event points, which are endpoints of the segments from our set, are known in advance. In contrast, the event points which represent intersection points of the segment from our set, are not known in advance. They're computed on the fly. Let us also consider an example of such situation. On the left, you see still the same set of segments, and the sweep line l is not about to reach the intersection point of the segments S_1 and S_2, labeled by z. At this very moment, the status contains three segments; S_1, S_2, and S_3. One average of the point z, the segments S_1 and S_2 exchange their order in the status. So, starting from this very moment, the status will be S_2, S_1, and S_3, and it will remain as such until the next event point is reached by the sweep line. To make sure no important aspect of plane sweep has escaped our attention, let us now consider step-by-step the entire process for this sample set of the three segments. Once again, initially the sweep line resides at the infinity, and the status represents an empty set. This is first changed at the moment when the sweep line reaches the upper endpoint from all the segment endpoints from our set. This is the upper endpoint of the segment as two, labeled by a_2. When this happens, the segment S_2 gets into status, which now consists of a single segment. The next event point to be reached is the upper endpoint of the segment S_1. When this happens, the intersection point of l with S_1, and namely the point a_1 lies to the left from the intersection point of the line l with the segment S_2. Therefore, now the status will have the form S_1 and S_2, and this will be precisely the order of those segments in it. Next, the sweep line will reach the upper endpoint of the segment S_3, labeled by a_3 The segment S_3 will appear in the status between the two segments already contained in it. Now, the status becomes S_1, S_3, and S_2. Subsequently, the sweep line l will reach the intersection point of the segments S_2 and S_3, labeled by z_23. At this moment, the segments S_2 and S_3 will change their order in the status and the status will become S_1, S_2, S_3. The next event point to be handled is the intersection point of the segments S_1 and S_2, which is labeled by z_12. Once again, this will lead to a change in the order of the segments S_1 and S_2 in the status. Now, the status will get the form S_2, S_1, S_3. Subsequently, the lower endpoint of the segment S_3 will be reached, and the last segment S_3 will be eliminated from the status. The next point to be processed in the lower endpoint of the segment S_2, and this will also lead to the elimination of the respective segment from the status. Only S_1 will remain under consideration and finally, we will also reach the lower endpoint of the segment S_1, and the status will become empty again. In our case, we have successfully passed all the endpoints of the segments from our sets, and other set itself, and so no more changes can occur to the status. This means that we are done.
