Check if two lines (each with start-end positions) overlap in python
Check if two lines (each with start-end positions) overlap in python
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?
2 Answers
2
Consider a span [a, b] and another span [x, y]. They either overlap or they are separate.
[a, b]
[x, y]
If they are separate, one of two things must be true:
[a, b]
[x, y]
[x, y]
[a, b]
If [a, b] is to the left of [x, y], we have b < x.
[a, b]
[x, y]
b < x
If [x, y] is to the left of [a, b], we have y < a.
[x, y]
[a, b]
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:
are_overlapping
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]
Your conditions are wrong; check them again. For instance, the first condition implies that (t_1, t_2) = (100, 200) and (s_1, s_2) = (50, 60) to be a valid set of overlapping lines. But clearly, they aren't.
(t_1, t_2) = (100, 200)
(s_1, s_2) = (50, 60)
Something else you might want to consider is if the user inputs the coordinates in backwards. What if he puts in something like '80-30'?
'80-30'
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
