Python/Pandas中高效统计未标记等宽条带数量的方法

给定一张零星印有文字/图案的纸张，需统计可裁剪出的指定宽度的未标记条带数量（不采用文本位置偏移裁剪等技巧）。数据以包含x0和x1列的pandas DataFrame形式提供，这两列是标记区域在对应维度的边界框数值。

我最初尝试用pd.cut()和DataFrame.groupby()，通过np.arange()划分区间并统计空区间数量，但这种方法仅在标记区域宽度（x1-x0）小于条带宽度时有效：

def count_unmarked_strips(df, total_width, strip_width):
    bins = np.arange(0, total_width, strip_width)
    count_min = df.groupby(pd.cut(df['x0'], bins=bins))['x0'].count().to_numpy()
    count_max = df.groupby(pd.cut(df['x1'], bins=bins))['x1'].count().to_numpy()
    return ((count_min + count_max) == 0).sum()

这个方法逻辑不够严谨，也无法扩展到标记区域宽度大于条带宽度的场景。本质上我想找一种高效的区间集合比较方法。

后来我写了另一个可行的方案，但运行速度较慢，希望能优化性能：

def count_unmarked_strips_alt(df, total_width, strip_width):
    bin_edges = np.arange(0, total_width, strip_width)
    bins = np.zeros(len(bin_edges)-1, dtype=bool)
    for i in range(len(bins)):
        bin_count = df.loc[
            ( # 标记起始于当前条带内
                (df['x0'] >= bin_edges[i])
                & (df['x0'] <= bin_edges[i+1])
            )
            | ( # 标记结束于当前条带内
                (df['x1'] >= bin_edges[i])
                & (df['x1'] <= bin_edges[i+1])
            )
            | ( # 标记横跨当前条带边界
                (df['x0'] <= bin_edges[i])
                & (df['x1'] >= bin_edges[i])
            )
        ].shape[0]
        bins[i] = bin_count == 0
    return bins.sum()

total_width = 20.
strip_width = 2. # 两个函数结果一致
# strip_width = 1. # 第一个函数会高估未标记条带数量

df = pd.DataFrame()
df['x0'] = [0.1, 6.3, 2.5, 17.2, 11.8, 5.3]
df['x1'] = [0.7, 7.9, 5.4, 19.0, 12.2, 5.7]

比如，一张宽度20cm的纸张上有6个标记区域，裁剪为2cm宽的条带时，最终有2条未标记的条带。

内容的提问来源于stack exchange，提问作者Idle_92