python - 有效地查找间隔/范围是否是较长间隔/范围的一部分

Question

我有一个排序的 numpy 2d 数组 x，每行中包含两个间隔的开始位置和结束位置:

[[x_start_1, x_end_1, y_start_1, y_end_1],
 [x_start_2, x_end_2, y_start_2, y_end_2],
 ...
 [x_start_n, x_end_n, y_start_n, y_end_n]]

该数组按 x_start_n 和 x_end_n 之间的长度降序排列。同一行的 x 和 y 间隔的长度始终相同。

问题是:如果给定行中的 x 和 y 间隔是任何 的子间隔，那么最有效和最好的解决方案是什么x 和 y 与上面任意行的间隔？

示例:

array([[35, 39,  1,  5],
       [20, 24,  4,  8],
       [32, 36, 10, 14],
       [35, 38,  1,  4], --> TRUE
       [35, 38, 21, 24],
       [19, 22,  2,  5],
       [36, 39,  2,  5], --> TRUE
       [20, 23,  4,  7], --> TRUE
       [      ...     ]])

我能想到并实现的唯一解决方案是执行双 for 循环并扩展有效行列表，并在下一次迭代中使用它进行比较。

为了更容易可视化:

1.      ---------    |         ---------
2.    -----          |           -----
3.        ---        |            ---          -> TRUE
4.             --    |                --       -> TRUE

感谢您的帮助! <3

Answer 1

这是利用 broadcasting 的矢量化方式-

m1 = x[:,0,None]<=x[:,0]
m2 = x[:,1,None]>=x[:,1]

m3 = x[:,2,None]<=x[:,2]
m4 = x[:,3,None]>=x[:,3]

m12 = m1 & m2
m34 = m3 & m4
out = np.triu((m12 & m34),1).any(0)

示例输入、输出 -

In [2]: x
Out[2]: 
array([[35, 39,  1,  5],
       [20, 24,  4,  8],
       [32, 36, 10, 14],
       [35, 38,  1,  4],
       [35, 38, 21, 24],
       [19, 22,  2,  5],
       [36, 39,  2,  5],
       [20, 23,  4,  7]])

In [3]: out
Out[3]: array([False, False, False,  True, False, False,  True,  True])