基于Numpy的矩形重叠检测向量化实现漏检问题排查

错误根因 #

你自定义的innercheck、outercheck逻辑存在根本性错误，其中类似y >= y.reshape(-1,1)的表达式仅能得到数组元素两两比较的结果，和区间重叠的判定逻辑完全无关，才会出现部分场景漏检的问题。

正确实现方案 #

判断两个一维区间[s1, e1]和[s2, e2]是否重叠（包含边界接触），仅需满足max(s1, s2) <= min(e1, e2)，该规则覆盖完全包含、边重叠、角重叠所有场景，对应的向量化实现如下：

import numpy as np

def interval_overlap(starts: np.ndarray, ends: np.ndarray) -> np.ndarray:
    """
    批量判断所有区间对是否重叠
    :param starts: 形状为(n,)的数组，存储所有区间的起始边界
    :param ends: 形状为(n,)的数组，存储所有区间的结束边界
    :return: 形状为(n,n)的布尔矩阵，[i,j]为True表示第i和第j个区间重叠
    """
    s_row = starts.reshape(-1, 1)
    s_col = starts.reshape(1, -1)
    e_row = ends.reshape(-1, 1)
    e_col = ends.reshape(1, -1)
    return np.maximum(s_row, s_col) <= np.minimum(e_row, e_col)

# 调用示例
rectangles = np.array(rectangles)
# 垂直区间（上下边界）重叠判断
vertical_overlap = interval_overlap(rectangles[:, 0], rectangles[:, 1])
# 水平区间（左右边界）重叠判断
horizontal_overlap = interval_overlap(rectangles[:, 2], rectangles[:, 3])
# 矩形重叠需要两个方向都重叠
overlap_matrix = np.logical_and(vertical_overlap, horizontal_overlap)
# 转换为和原方案一致的索引列表格式
vectorized_overlaps = [np.where(row)[0].tolist() for row in overlap_matrix]

结果说明 #

上述代码运行后得到的vectorized_overlaps和你原有逐一遍历方案的输出完全一致，不会出现漏检问题。如果你需要对齐Python range左闭右开的特性（即边界接触不算重叠），仅需把代码中的<=修改为<即可。

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