如何寻找中心对齐矩阵的重叠单元格及特定单元格匹配方案

前提定义 #

所有矩阵的单元格为轴对齐的单位正方形，坐标采用0-based：

• 单元格(row, col)对应的几何区域是 [row, row+1) × [col, col+1)，中心坐标为 (row+0.5, col+0.5)
• 两个矩阵整体几何中心对齐：即矩阵A的中心(M_A/2, N_A/2)与矩阵B的中心(M_B/2, N_B/2)完全重合（M为行数，N为列数）

问题1：找出两个矩阵的所有重叠单元格 #

通用逻辑 #

判断矩阵中某个单元格是否属于重叠区域，只需检查该单元格的几何范围与另一矩阵的整体范围是否有交集：

1. 对于矩阵A（M₁行N₁列）的单元格(r₁,c₁)，满足以下条件则与矩阵B（M₂行N₂列）重叠：

   r₁ + 1 > (M₁ - M₂)/2
   r₁ < (M₁ + M₂)/2
   c₁ + 1 > (N₁ - N₂)/2
   c₁ < (N₁ + N₂)/2
   

2. 同理，矩阵B的单元格(r₂,c₂)与矩阵A重叠的条件：

   r₂ + 1 > (M₂ - M₁)/2
   r₂ < (M₂ + M₁)/2
   c₂ + 1 > (N₂ - N₁)/2
   c₂ < (N₂ + N₁)/2
   

3. 筛选出所有符合条件的单元格，即为各自的重叠区域。

示例验证（红矩阵5×4，绿矩阵2×2） #

• 红矩阵重叠单元格：
  行范围：r₁ > 0.5 且 r₁ < 3.5 → r₁=1,2,3
  列范围：c₁ > 0 且 c₁ < 3 → c₁=1,2
  最终重叠单元格：{(1,1), (2,1), (3,1), (1,2), (2,2), (3,2)}
• 绿矩阵重叠单元格：所有行、列均满足条件，因此全部单元格属于重叠区域。

问题2：给定单个单元格，找出另一矩阵中与之重叠的单元格 #

通用逻辑 #

1. 将目标单元格的几何范围转换到另一矩阵的坐标系（利用中心对齐的平移关系）：
   矩阵A的单元格(r₁,c₁)在矩阵B坐标系中的范围为：

   [r₁ + (M₂-M₁)/2, r₁+1 + (M₂-M₁)/2) × [c₁ + (N₂-N₁)/2, c₁+1 + (N₂-N₁)/2)
   

2. 找出矩阵B中所有与上述范围有交集的单元格，即满足：

   r₂ < r₁+1 + (M₂-M₁)/2
   r₂+1 > r₁ + (M₂-M₁)/2
   c₂ < c₁+1 + (N₂-N₁)/2
   c₂+1 > c₁ + (N₂-N₁)/2
   

3. 解不等式得到有效行、列范围，生成所有符合条件的单元格坐标。

示例验证（红矩阵(2,1) → 绿矩阵重叠单元格） #

• 代入参数：M₁=5, N₁=4, M₂=2, N₂=2, r₁=2, c₁=1
• 行范围：r₂ > -0.5 且 r₂ < 1.5 → r₂=0,1
• 列范围：c₂ > -1 且 c₂ < 1 → c₂=0
• 最终重叠单元格：{(0,0), (1,0)}

通用算法（支持任意维度矩阵） #

以上逻辑对任意维度的矩阵（如4×5与5×4）均适用，可通过以下伪代码实现：

问题1伪代码 #

import math

def get_overlapping_cells(m1, n1, m2, n2):
    # 计算矩阵1的重叠单元格
    row_min1 = math.ceil((m1 - m2)/2)
    row_max1 = math.floor((m1 + m2)/2) - 1
    col_min1 = math.ceil((n1 - n2)/2)
    col_max1 = math.floor((n1 + n2)/2) - 1
    # 边界修正
    row_min1 = max(row_min1, 0)
    row_max1 = min(row_max1, m1-1)
    col_min1 = max(col_min1, 0)
    col_max1 = min(col_max1, n1-1)
    overlap1 = [(r,c) for r in range(row_min1, row_max1+1) for c in range(col_min1, col_max1+1)]
    
    # 计算矩阵2的重叠单元格
    row_min2 = math.ceil((m2 - m1)/2)
    row_max2 = math.floor((m2 + m1)/2) - 1
    col_min2 = math.ceil((n2 - n1)/2)
    col_max2 = math.floor((n2 + n1)/2) - 1
    row_min2 = max(row_min2, 0)
    row_max2 = min(row_max2, m2-1)
    col_min2 = max(col_min2, 0)
    col_max2 = min(col_max2, n2-1)
    overlap2 = [(r,c) for r in range(row_min2, row_max2+1) for c in range(col_min2, col_max2+1)]
    
    return overlap1, overlap2

问题2伪代码 #

import math

def get_corresponding_cells(r1, c1, m1, n1, m2, n2):
    # 计算行范围
    row_low = r1 + (m2 - m1)/2
    row_high = r1 + 1 + (m2 - m1)/2
    r_min = math.floor(row_low - 1) + 1
    r_max = math.ceil(row_high) - 1
    r_min = max(r_min, 0)
    r_max = min(r_max, m2-1)
    
    # 计算列范围
    col_low = c1 + (n2 - n1)/2
    col_high = c1 + 1 + (n2 - n1)/2
    c_min = math.floor(col_low - 1) + 1
    c_max = math.ceil(col_high) - 1
    c_min = max(c_min, 0)
    c_max = min(c_max, n2-1)
    
    return [(r,c) for r in range(r_min, r_max+1) for c in range(c_min, c_max+1)]

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