Check if two lines (each with start-end positions) overlap in python
algorithm, python
Solution
Consider a span `[a, b]` and another span `[x, y]`. They either overlap or they are separate.
If they are separate, one of two things must be true:
- `[a, b]` is to the left of `[x, y]`, or
- `[x, y]` is to the left of `[a, b]`.
If `[a, b]` is to the left of `[x, y]`, we have `b < x`.
If `[x, y]` is to the left of `[a, b]`, we have `y < a`.
If neither of these is true, the spans cannot be separate. They must overlap.
This logic is implemented in the following function.
def are_separate(r, s): # r and s are ordered pairs
(a, b) = r
(x, y) = s
if b < x or y < a:
return True
else:
return False
More concisely:
def are_separate(r, s):
(a, b) = r
(x, y) = s
return b < x or y < a
Even more concisely:
def are_separate(r, s):
return r[1] < s[0] or s[1] < r[0]
If you want the contrary function, `are_overlapping`, just negate the expression:
def are_overlapping(r, s):
return not(r[1] < s[0] or s[1] < r[0])
Which is logically equivalent to:
def are_overlapping(r, s):
return r[1] >= s[0] and s[1] >= r[0]
Problem
I have the following two sets of position each correspond to the start and end position: ``` line T: t1-t2 (t1 = start_pos, t2 = end_pos) line S: s1-s2 (s1 = start_pos, t2 = end_pos) ``` I want to write the algorithm in Python to check if T intersect with S. Example 1: ``` t1-t2=55-122 and s1-s2=58-97 s1------------s2 t1-----------------t2 This should return True ``` Example 2: ``` t1-t2=4-66 / t1-t2=143-166 and s1-s2=80-141 s1----s2 t1--t2 t1---t2 Both instances of T should return False ``` But why this code failed: ``` def is_overlap(pos, dompos): """docstring for is_overlap""" t1,t2 = [int(x) for x in pos.split("-")] s1,s2 = [int(x) for x in dompos.split("-")] # Here we define the instance of overlapness if (t1 >= s1 and t2 >= s2) or \ (t1 >= s1 and t2 <= s2) or \ (t1 <= s1 and t2 >= s2) or \ (t1 <= s1 and t2 <= s2): return True else: return False ``` which output this: ``` In [2]: is_overlap('55-122', '58-97') Out[2]: True In [3]: is_overlap('4-66', '80-141') Out[3]: True In [4]: is_overlap('143-166', '80-141') Out[4]: True ``` What's the right way to do it?