Web
Analytics Made Easy - StatCounter

Check if any two line segments intersect given n line segments

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.

  1. Check if two line segments intersect.
  2. Determining if two segments turn left or right
  3. Red Black Tree

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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
2
3
4
5
6
7
8
9
10
11
12
class Point:
def __init__(self, x, y, ptype = 0):
self.x = x
self.y = y
self.ptype = ptype # 0 means left, 1 means right
self.other_end = None

def subtract(self, p):
return Point(self.x - p.x, self.y - p.y)

def __str__(self):
return '(' + str(self.x) + ', ' + str(self.y) + ')'

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def __insert_helper(self, z):
print z.key
y = NilNode.instance()
x = self.root
while x:
y = x
if direction(x.key, x.key.other_end, z.key) < 0:
x = x.left
else:
x = x.right

z.parent = y
if not y:
self.root = z
else:
if direction(y.key, y.key.other_end, z.key) < 0:
y.left = z
else:
y.right = z

self.size += 1

The implementation of the Line Sweep Algorithm given in above section is given below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def compare(p1, p2):
if p1.x < p2.x:
return -1
elif p1.x > p2.x:
return 1

if p1.x == p2.x:
if p1.ptype == p2.ptype:
if p1.y < p2.y:
return -1
else:
return 1
else:
if p1.ptype == 0:
return -1
else:
return 1

def any_segments_intersect(S):
# Step 1
T = RedBlackTree()

# Step 2
sortedS = sorted(S, cmp=lambda x,y: compare(x,y))
sortedS = map(lambda x: Node(x), sortedS)

# Step 3
for point in sortedS:
if point.key.ptype == 0:
T.insert(point)
prd = T.predecessor(point)
if prd and intersect(point.key, point.key.other_end, prd.key, prd.key.other_end):
return True
ssc = T.successor(point)
if ssc and intersect(point.key, point.key.other_end, ssc.key, ssc.key.other_end):
return True
if point.key.ptype == 1:
prd = T.predecessor(point)
ssc = T.successor(point)

if prd and ssc:
if intersect(prd.key, prd.key.other_end, ssc.key, ssc.key.other_end):
return True
T.delete(point)
return False

Complexity

The total complexity of the algorithm is calculated step-by-step below.

  1. To sort the endpoints of the segments we spend $(2n\log n)$ time as there are $2n$ endpoints of $n$ segments.
  2. 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

  1. Erickson, J. (n.d.). Line Segment Intersection. Retrieved August 22, 2018, from http://jeffe.cs.illinois.edu/teaching/373/notes/x06-sweepline.pdf
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.