What is the Line Sweep Algorithm?
The line sweep algorithm is an algorithm used to find intersections between line segments. The line sweep algorithm will make some observations about how intersections work between line segments to speed up the process. Some applications of the line sweep algorithm might include putting a bridge whenever a road and water line segment are interested in each other.
The Line Sweep Algorithm:
In the line sweep algorithm, a horizontal line will start at the very top and then slowly move down. In order to narrow down what values need to be checked at each point in time, the line sweep algorithm will create event points at a y value for each end point of every line segment. The horizontal line sweep line only needs to stop at the event points, as every other point will make no changes, meaning this scenario has already been calculated.
As the line visits the event points, When it reaches the top endpoint of a line segment, it will add it to a group that may potentially intersect with each other. When it reaches the bottom end point of a line segment, it no longer needs to be considered as it no longer exists in the new search space.
The people who invented the line sweep algorithm also made another important observation about the domains (where they exist in terms of x) of each of the line segments. It is impossible for two lines to intersect if there is a line in between them that doesn’t intersect one of them. So, at each event point, only a few lines actually needed to be tested because of this property. Assuming these three lines are currently being considered, it is impossible for the red line and the blue line to intersect without one of them having to pass through the black line in the middle. So, for each line segment in the line sweep, If it doesn’t currently intersect with any of its direct neighbors, then there doesn’t need to be any more searching, as it is currently impossible.
Whenever a intersection is found a new event also needs to be established.
Specifics on Line Sweep:
Storing some of the values:
The first value that needs to be stored is the location of the event points. Since our sweep line will go from top to bottom, a data structure such as a balanced binary search tree can be used. It allows us to add, delete, and find values in O (log n). In most implementations of line sweep, when there are multiple points that share the same y value, they are ordered from left to right using their x values. Now for storing the horizontal order of the lines. This will be used to prove whether two lines even have a chance of intersecting. This will also be done with a balanced binary search tree.
Finding the exact intersection point:
Each line segment can be looked at as a bouded line equation. Think of it as y = mx + b, which only exists between some interval of x values. The slope can be obtained by using the two points of the line segment. The y-intercept can be determined by setting y = 0. Every line segment will be in y = mx + b, so when comparing two lines, they can just be compared to each other to produce mx + b = mx + b (where both equations are obviously different). The previous equation will yield the x value, and plugging the x value into either of the line segments will produce the y value, giving the (x,y) pair.
More about the algorithm
While running the algorithm, there will be three different sets. For each event point, a line segment might be touching with its bottom end point, upper end point, or it passes straight through it. These sets will be denoted as L(p), U(p), and C(p), respectively. While moving the line down at each event point, there needs to be a function that deals with the current situation. The function will have the following functionality:
If the union between sets U(p), L(p), and C(p) is greater than 1, then there is an intersection at the current point.
It will also delete the union between L (p) and C (p). There is no reason to continue having the line segment, which no longer exists according to the sweep line.
It will also insert the union between U (p) and C (p). This will include the new points that are now intersecting the sweep line.
If the set U(p) unioned with C(p) is empty, Then there is the potential for more intersection points. As stated previously, two line segments cannot intersect if there is a line between them that neither of them intersects. Now that certain lines are gone, it might be possible that two lines previously deemed impossible to inert might have changed their state. This means finding new intersections and establishing more event points.
Take the left and right neighbors of the current event point.
If there is no intersection, nothing needs to happen.
If there is an intersection that takes place either left of the event point or above the event point, it doesn’t need to be considered. This is due to the nature of the sweep line, which would have already accounted for that point before.
If the new intersection exists either to the right or below the event point, then a new event point needs to be made at that point for future analysis.
Other new neighbors might need to be established. In this case, take the leftmost segments from the union of U(p) and C(p). For the second leftmost line, assign it a new left neight, and for the second rightmost line, assign it a new right neighbor. If there is only one line, then it is possible that it is being assigned two new neighbors.