Check if two lines (each with start-end positions) overlap in python

Question

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?

Answer 1

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]