笛卡尔坐标系中覆盖指定点的矩形高效搜索算法咨询

现有一组由数组构成的矩形数据集，每个数组包含X轴起止点（Xs, Xe）与Y轴起止点（Ys, Ye）四个坐标值，示例如下：

Xs|Xe|Ys|Ye
--------------
[[10,15,5,8],
 [9,12,5,8],
 [1,20,1,20]]

给定一点(x,y)，当前采用遍历所有数组逐一比较的方式筛选覆盖该点的矩形，Python实现代码如下：

related_rectangles = []
for rectangle in dataset:
    if x > rectangle[0] and x < rectangle[1] and y > rectangle[2] and y < rectangle[3]:
        related_rectangles.append(rectangle)

该方法时间复杂度为O(n)。现咨询是否存在可降低搜索复杂度的算法或数据结构，尤其针对所有图形均为正方形的场景。

通用矩形场景（含正方形） #

1. 空间划分类数据结构 #

• 二维区间树：以矩形的X轴区间构建主区间树，每个节点关联对应矩形的Y轴区间结构。查询时先通过X轴筛选出包含x的矩形集合，再在该集合内通过Y轴筛选包含y的矩形，查询复杂度为O(log n + k)，其中k是匹配到的矩形数量。
• 四叉树：将整个空间递归划分为四个象限，矩形存储在其覆盖的所有象限节点中。查询时仅遍历包含点(x,y)的象限及其父节点内的矩形，适合矩形分布均匀的场景，平均查询效率优于O(n)。

2. 排序+二分查找优化 #

先将所有矩形按Xs升序排序，同时预处理每个位置对应的Xe最大值数组。查询时通过二分找到所有Xs < x的矩形，再筛选其中Xe > x的；接着对筛选后的矩形按Ys/Ye重复二分筛选，最终得到符合条件的矩形。该方法将线性扫描转为多次二分查找，复杂度降至O(log n + k)。

正方形特化场景 #

利用正方形Xe - Xs = Ye - Ys = 边长的特性，可进一步优化：

• 按边长分组：将正方形按边长分成不同组别，查询时先计算能包含(x,y)的正方形边长范围，仅在对应边长组内搜索，直接缩小数据集规模。
• 中心坐标索引：计算每个正方形的中心坐标(cx, cy) = ((Xs+Xe)/2, (Ys+Ye)/2)和半径r = 边长/2，点(x,y)在正方形内等价于|x - cx| < r 且 |y - cy| < r。将中心坐标构建成二维KD树，查询时先找出中心与(x,y)距离小于最大可能半径的正方形，再验证上述不等式，大幅减少候选验证数量，效率比通用结构更高。

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