确定一个区间是否包含于另一个区间中。

Question

如果有一个按第一列排序的区间文件（没有重叠区间）：

1 10
12 15
18 19

另一个示例，按第一列排序（可能有重叠）：

1 5
2 10
12 13
13 20

我希望确定第二个文件中每一行（范围）是否与第一个文件中的任何范围相交。到目前为止，我已经做了以下工作：

df_1 = pd.read_csv('range1.txt',sep=' ')
df_2 = pd.read_csv('range2.txt',sep=' ')

for i in xrange(len(df_1)):
    start_1 = df_1.iloc[i,0]
    stop_1 = df_1.iloc[i, 1]
    for j in xrange(len(df_2)):
        start_2 = df_2.iloc[j,0]
        stop_2 = df_2.iloc[j, 1]
        if start_2 > stop_1:
            break
        elif stop_2 < start_1:
            continue
        else:
            # add ranges from second file to list

我知道这可能非常低效，因此我想知道是否有更加计算有效/更快的方法来解决这个问题。

- user2958395

---

您可以在 https://en.wikipedia.org/wiki/Interval_tree 中找到更高效的算法。 - Olivier Pellier-Cuit

看起来你打错了：应该使用j作为索引而不是i来设置start_2 = df_2.iloc[j, 0]; stop_2 = df_2.iloc[j, 1]。除此之外，我认为这段代码已经尽可能地高效了。 - Jon McClung

Answer 1

@Olivier Pellier-Cuit 提供了一个快速重叠测试的链接。如果您需要会员资格检查而不是重叠测试，请使用此算法。

因此，使用此算法，我们可以执行以下操作：

df1['m'] = (df1.a + df1.b)
df1['d'] = (df1.b - df1.a)

df2['m'] = (df2.a + df2.b)
df2['d'] = (df2.b - df2.a)

df2[['m','d']].apply(lambda x: (np.abs(df1.m - x.m) < df1.d +x.d).any(), axis=1)

PS我稍微简化了m和d的计算，通过消除公共项来摆脱2的除法。

输出：

In [105]: df2[['m','d']].apply(lambda x: (np.abs(df1.m - x.m) < df1.d +x.d).any(), axis=1)
Out[105]:
0     True
1     True
2     True
3     True
4    False
dtype: bool

设置：

df1 = pd.read_csv(io.StringIO("""
a b
1 10
12 15
18 19
"""), delim_whitespace=True)

df2 = pd.read_csv(io.StringIO("""
a b
1 5
2 10
12 13
13 20
50 60
"""), delim_whitespace=True)

注意：我特意向DF2中添加了一对（50，60），它与DF1中的任何区间都不重叠。

具有计算出的“m”和“d”列的数据框：

In [106]: df1
Out[106]:
    a   b   m  d
0   1  10  11  9
1  12  15  27  3
2  18  19  37  1

In [107]: df2
Out[107]:
    a   b    m   d
0   1   5    6   4
1   2  10   12   8
2  12  13   25   1
3  13  20   33   7
4  50  60  110  10

- MaxU - stand with Ukraine

Answer 2

如果您只想知道df2的范围是否与df1的范围重叠： if df1.ix [:，0] .min（）> = df2.ix [:，0] .max（）或df1.ix [:，0] .max（）< = df2.ix [:，0] .min（）： print（“nope”） 否则： print（“overlap”）

- Andreas Hsieh

---

我想知道 df_2 中的每一行（范围）是否与 df_1 中的任何一行（范围）相交。我将更新问题以包括这一点。 - user2958395