如何高效检测并移除被包含的矩形？（10000条矩形数据集场景）

首先，你的原始双重循环方案对于10000个矩形来说时间复杂度是O(n²)，纯Python循环会慢到无法接受——毕竟1e8次迭代可不是闹着玩的。下面给你两种高效的解决方案，从易上手到更优化的版本：

方案一：Numpy向量化实现（易上手，适合1e4规模） #

利用Numpy的向量运算能力，把原本的双重循环转化为底层C实现的矩阵操作，速度会提升几个数量级。核心思路是直接对每个矩形，检查是否存在其他矩形满足左边界≤当前左、上边界≤当前上、右边界≥当前右、下边界≥当前下的包含条件（这里假设坐标系是y轴向下，左上角(b)数值越小越靠上，右下角(d)数值越大越靠下；如果你的坐标系是y轴向上，只需要调整b和d的比较符号即可）。

import pandas as pd
import numpy as np

def remove_contained_rectangles(file_path):
    # 加载数据
    df = pd.read_csv(file_path)
    # 先过滤掉无效矩形（确保右边界>左边界，下边界>上边界）
    df = df[(df['c'] > df['a']) & (df['d'] > df['b'])].reset_index(drop=True)
    if df.empty:
        return df
    
    # 提取各边界的numpy数组，方便向量运算
    a = df['a'].values  # 左x
    b = df['b'].values  # 上y
    c = df['c'].values  # 右x
    d = df['d'].values  # 下y
    
    # 构建包含矩阵：contains[j, i] 表示矩形j完全包含矩形i
    contains = (a[:, np.newaxis] <= a) & \
               (b[:, np.newaxis] <= b) & \
               (c[:, np.newaxis] >= c) & \
               (d[:, np.newaxis] >= d)
    
    # 排除矩形自身包含自身的情况（对角线元素设为False）
    np.fill_diagonal(contains, False)
    
    # 判断每个矩形是否被其他任何矩形包含
    is_contained = contains.any(axis=0)
    
    # 保留未被包含的矩形
    return df[~is_contained]

# 使用示例
result = remove_contained_rectangles('dataset.csv')
result.to_csv('filtered_dataset.csv', index=False)

这个方案的内存占用大概是100MB左右（1e4×1e4的布尔矩阵），对于现代电脑完全没问题，运行时间大概在几秒内。

方案二：排序+贪心算法（O(n log n)时间，适合更大规模） #

如果你的数据集未来可能超过1e4，比如到1e5级别，向量化方案的内存就会不够用了。这时候可以用排序+贪心的思路，把问题降维处理：

1. 排序规则：先按左边界(a)升序，右边界(c)降序，上边界(b)升序，下边界(d)降序排序。这样排序后，对于任意i < j，矩形i的左边界≤j的左边界，右边界≥j的右边界——也就是说，j的x范围完全在i的x范围内。此时，判断i是否包含j只需要看y轴的边界：i的上边界≤j的上边界，且i的下边界≥j的下边界。

2. 贪心筛选：维护一个候选列表，里面存储目前找到的未被包含的矩形。遍历排序后的每个矩形，只需要检查候选列表中是否存在矩形满足y轴的包含条件即可。

import pandas as pd

def remove_contained_rectangles_optimized(file_path):
    df = pd.read_csv(file_path)
    df = df[(df['c'] > df['a']) & (df['d'] > df['b'])].reset_index(drop=True)
    if df.empty:
        return df
    
    # 按左边界升序、右边界降序、上边界升序、下边界降序排序
    sorted_df = df.sort_values(by=['a', 'c', 'b', 'd'], ascending=[True, False, True, False])
    candidates = []  # 存储(d, b)，保持d降序排列
    keep_indices = []
    
    for idx, row in sorted_df.iterrows():
        current_b = row['b']
        current_d = row['d']
        contained = False
        
        # 候选列表按d降序，一旦遇到d小于当前d的，后面的都不用看了
        for d_candidate, b_candidate in candidates:
            if d_candidate < current_d:
                break
            if b_candidate <= current_b:
                contained = True
                break
        
        if not contained:
            keep_indices.append(idx)
            # 加入候选并保持d降序
            candidates.append((current_d, current_b))
            candidates.sort(reverse=True, key=lambda x: x[0])
    
    return sorted_df.loc[keep_indices].reset_index(drop=True)

这个贪心算法的内存占用极小，而且因为候选列表的长度通常远小于n，实际运行效率也很高。

为什么你的原始方案慢？ #

原始的双重Python循环，每次迭代都要做边界判断，1e4个矩形就是1e8次迭代，Python的单线程处理这种循环非常慢，而Numpy的向量运算把这些操作放到底层C实现，速度能提升几百倍甚至上千倍。

内容的提问来源于stack exchange，提问作者Sri Sanketh Uppalapati