Introduction
Before going through this article, make sure to visit the following articles. Many code segments are referred from these articles without writing them here explicitly.
In this article, we discussed a way to determine if two line segments intersect. Here, we extend the ideas to $n$ line segments and determine if any two of the $n$ line segments intersect. We use a line sweep algorithm to find the intersections in $O(n\log n)$ time.
Algorithm
Given $n$ line segments as shown in the figure (although only 5 segments are shown), the Line Sweep Algorithm works as follows.
- All the endpoints (there are $2n$ endpoints total) are sorted in increasing value of x-coordinate. If more than one points have the same x-coordinate, the left endpoint will get priority over the right endpoint. If the endpoints are of the same type i.e. all left or all right, then we select endpoint with lower y-coordinate first. This operation must take $O(n\log n)$ time.
- The sorted endpoints are scanned from left to right one at a time. If the endpoint is left endpoint, we insert the corresponding segment into a data structure $T$ above or below the old segment. If the left end of the new segment is above the old segment, we insert the new segment above the old segment otherwise we insert the new segment below the old segment. This operation must take $O(\log n)$ time.
- Once the segment is inserted, we test if the new segment intersects the segment below or above it. Finding the segment above or below it should take $O(\log n)$ time and check if they intersect should take constant time.
- When the sweep line hits a right endpoint, we delete it from $T$ in $O(\log n)$ time. We test if the segment before and after it intersects.
Program
In this section, we implement Line Sweep Algorithm in python. The program needs two data structures. One for representing a point (I am using point to represent a segment as well using some tricks) and another for storing the segments while the Line Sweep Algorithm is in progress (we denoted this structure with $T$ above). The point data structure is simple as shown in the code below
1 | class Point: |
Point has four properties. Properties x
and y
represents $x$ and $y$ coordinates. Property ptype
distinguishes left endpoint from the right endpoint. If it is a left endpoint then property other_end
holds the right endpoint of a segment. Two additional properties ptype
and other_end
can make the point acts as a segment.
To store the segments, we need a special kind of data structure where the operations insert, delete and search take only $O(\log n)$ time. A good choice for such data structure would be a Red Black Tree. I have used an already implemented Red Black Tree written by Charles Oliver Nutter with a little modification in the insert method considering the insertion rule given in Solution section of this article. The modified method is given below.
1 | def __insert_helper(self, z): |
The implementation of the Line Sweep Algorithm given in above section is given below.
1 | def compare(p1, p2): |
Complexity
The total complexity of the algorithm is calculated step-by-step below.
- To sort the endpoints of the segments we spend $(2n\log n)$ time as there are $2n$ endpoints of $n$ segments.
- For each segment, we insert the left endpoint in $O(\log n)$ time, delete the right endpoint in $O(\log n)$ and search the predecessor and successor in $O(\log n)$. The total time is, therefore, $2n * c\log n$. Which is $O(n\log n)$.
Therefore the total complexity of this algorithm is $O(n\log n)$
References
- Erickson, J. (n.d.). Line Segment Intersection. Retrieved August 22, 2018, from http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.