python - 检查两条线(每条线都有起点和终点)在python中是否重叠

Question

我有以下两组位置分别对应开始和结束位置:

line T: t1-t2   (t1 = start_pos, t2 = end_pos)
line S: s1-s2   (s1 = start_pos, t2 = end_pos)

我想用 Python 编写算法来检查 T 是否与 S 相交。

示例 1:

   t1-t2=55-122 and s1-s2=58-97
          s1------------s2
        t1-----------------t2
    This should return True

示例 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

但是为什么这段代码失败了:

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

输出这个:

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

正确的做法是什么？

Answer 1

考虑跨度 [a, b]和另一个跨度 [x, y] .它们要么重叠，要么分开。

如果它们是分开的，则以下两个条件之一必须为真:

• [a, b]在 [x, y] 的左边, 或
• [x, y]在 [a, b] 的左边.

如果[a, b]在 [x, y] 的左边, 我们有 b < x .

如果[x, y]在 [a, b] 的左边, 我们有 y < a .

如果这些都不成立，则跨度不能分开。它们必须重叠。

此逻辑在以下函数中实现。

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

更简洁:

def are_separate(r, s):
  (a, b) = r
  (x, y) = s
  return b < x or y < a

更简洁:

def are_separate(r, s):
  return r[1] < s[0] or s[1] < r[0]

如果你想要相反的功能，are_overlapping , 只是否定表达式:

def are_overlapping(r, s):
  return not(r[1] < s[0] or s[1] < r[0])

这在逻辑上等同于:

def are_overlapping(r, s):
  return r[1] >= s[0] and s[1] >= r[0]