寻找目标矩形四向最近邻的高效算法及候选选择逻辑

一、如何找到对应方向的最近矩形 #

要解决这个问题，核心是先明确方向的有效候选范围，再计算符合直觉的方向距离，而非通用空间距离：

1. 定义各方向的有效候选矩形 #

假设矩形用(x1, y1, x2, y2)表示（x1=左边界，x2=右边界，y1=下边界，y2=上边界），活跃矩形记为R，各方向筛选条件如下：

• 向上方向：候选矩形的y2 ≤ R.y1（在R上方且不重叠），且x轴投影与R有交集（候选.x1 ≤ R.x2 且 候选.x2 ≥ R.x1）——确保是R正上方区域的矩形，而非左上/右上的角落矩形。
• 向下方向：候选矩形的y1 ≥ R.y2（在R下方且不重叠），且x轴投影与R有交集。
• 向左方向：候选矩形的x2 ≤ R.x1（在R左侧且不重叠），且y轴投影与R有交集（候选.y1 ≤ R.y2 且 候选.y2 ≥ R.y1）。
• 向右方向：候选矩形的x1 ≥ R.x2（在R右侧且不重叠），且y轴投影与R有交集。

2. 计算方向专属的最短距离 #

对筛选后的有效候选，计算轴对齐的方向距离（这是符合用户直觉的“最近”，而非空间直线距离）：

• 向上：距离 = R.y1 - 候选.y2
• 向下：距离 = 候选.y1 - R.y2
• 向左：距离 = R.x1 - 候选.x2
• 向右：距离 = 候选.x1 - R.x2

取距离最小的矩形，即为对应方向的最近矩形。

这种方法规避了顶点/质心距离的误区：比如顶点距离可能选中角落最近的斜向矩形，质心距离可能选中斜上方但空间距离更近的矩形，而轴对齐方向距离严格对应用户按键的“上下左右”意图。

二、等距最近矩形的选择规则 #

当同一方向存在多个等距候选时，设定以下优先级规则，优先匹配用户直觉：

• 上下方向等距：
  1. 优先选择与R的x轴重叠长度最长的矩形（重叠长度 = min(R.x2, 候选.x2) - max(R.x1, 候选.x1)）——重叠越多，越接近“正上下方”。
  2. 若重叠长度相同，选择x轴中点最接近R的x轴中点的矩形（R的x中点 = (R.x1 + R.x2)/2，候选同理）。
• 左右方向等距：
  1. 优先选择与R的y轴重叠长度最长的矩形。
  2. 若重叠长度相同，选择y轴中点最接近R的y轴中点的矩形。

示例场景适配 #

针对你提到的蓝色活跃矩形场景：

• 向上：筛选正上方区域的有效候选，计算方向距离取最小，若等距则按x重叠/中点规则选择。
• 向右：筛选右侧区域的有效候选，计算方向距离取最小，若等距则按y重叠/中点规则选择。
• 向下：同理筛选下方区域候选，按规则选出目标矩形。

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