求在field内生成与window无重叠的高维box的通用鲁棒算法（Python/NumPy）

核心思路 #

在高维空间中，两个矩形无重叠且无公共点的充要条件是：存在至少一个维度，box在该维度上的投影完全位于window投影的左侧（或右侧）。基于这个特性，我们可以避开枚举所有维度组合的繁琐操作，先选定一个「分隔维度」，再在该维度上生成满足分离条件的box坐标，最后在其余维度上生成完全处于field内的坐标即可。

算法步骤 #

• 定义高维矩形表示：用两个NumPy数组分别存储左下角（LL）和右上角（UR）坐标，数组长度等于空间维度数。例如field_ll、field_ur、window_ll、window_ur均为shape=(d,)的数组，d为维度数。
• 随机选择分隔维度：从0到d-1中随机选取一个维度k，作为box与window分离的维度。
• 生成分隔维度的box坐标：
  • 两种分离方向二选一：box的UR[k] ≤ window_ll[k] - 1（box在window左侧），或box的LL[k] ≥ window_ur[k] + 1（box在window右侧），随机选择其中一种。
  • 按方向生成坐标：
    • 左侧分离：box_ll[k]取值范围为[field_ll[k], window_ll[k] - 1 - box_size[k] + 1]，box_ur[k] = box_ll[k] + box_size[k] - 1（保证整数坐标且不超范围）
    • 右侧分离：box_ur[k]取值范围为[window_ur[k] + 1, field_ur[k]]，box_ll[k] = box_ur[k] - box_size[k] + 1（同样保证整数范围）
      注：box_size是预先定义的box各维度长度数组，需满足每个维度上box_size[k] ≤ field_ur[k] - field_ll[k] + 1，且分隔维度的剩余空间足够容纳box
• 生成其余维度的box坐标：对于非分隔维度i≠k，box_ll[i]取值范围为[field_ll[i], field_ur[i] - box_size[i] + 1]，box_ur[i] = box_ll[i] + box_size[i] - 1，直接随机生成即可。
• 可选验证：生成后可验证box完全在field内且与window无重叠无公共点，进一步保证鲁棒性。

Python + NumPy 代码实现 #

import numpy as np

def generate_non_overlapping_box(field_ll, field_ur, window_ll, window_ur, box_size):
    """
    生成高维空间中与window无重叠无公共点的box，完全位于field内
    参数：
        field_ll: np.ndarray, shape=(d,), field的左下角坐标
        field_ur: np.ndarray, shape=(d,), field的右上角坐标
        window_ll: np.ndarray, shape=(d,), window的左下角坐标
        window_ur: np.ndarray, shape=(d,), window的右上角坐标
        box_size: np.ndarray, shape=(d,), box各维度的长度（整数）
    返回：
        box_ll: np.ndarray, shape=(d,), box的左下角坐标
        box_ur: np.ndarray, shape=(d,), box的右上角坐标
    """
    d = len(field_ll)
    # 提前校验参数合法性
    assert np.all(box_size >= 1), "box各维度长度至少为1"
    assert np.all(box_size <= field_ur - field_ll + 1), "box尺寸超过field范围"
    
    # 随机选分隔维度
    sep_dim = np.random.randint(d)
    # 随机选分离方向：0=左侧，1=右侧
    direction = np.random.randint(2)
    
    box_ll = np.zeros(d, dtype=int)
    box_ur = np.zeros(d, dtype=int)
    
    if direction == 0:
        # 左侧分离逻辑
        max_ll_sep = window_ll[sep_dim] - 1 - box_size[sep_dim] + 1
        assert max_ll_sep >= field_ll[sep_dim], "左侧空间不足以容纳box"
        box_ll[sep_dim] = np.random.randint(field_ll[sep_dim], max_ll_sep + 1)
        box_ur[sep_dim] = box_ll[sep_dim] + box_size[sep_dim] - 1
    else:
        # 右侧分离逻辑
        min_ur_sep = window_ur[sep_dim] + 1
        assert min_ur_sep + box_size[sep_dim] - 1 <= field_ur[sep_dim], "右侧空间不足以容纳box"
        box_ur[sep_dim] = np.random.randint(min_ur_sep + box_size[sep_dim] - 1, field_ur[sep_dim] + 1)
        box_ll[sep_dim] = box_ur[sep_dim] - box_size[sep_dim] + 1
    
    # 处理非分隔维度
    for dim in range(d):
        if dim == sep_dim:
            continue
        max_ll_dim = field_ur[dim] - box_size[dim] + 1
        box_ll[dim] = np.random.randint(field_ll[dim], max_ll_dim + 1)
        box_ur[dim] = box_ll[dim] + box_size[dim] - 1
    
    # 可选校验：确保生成结果符合要求
    assert np.all(box_ll >= field_ll) and np.all(box_ur <= field_ur), "box超出field范围"
    assert (box_ur[sep_dim] <= window_ll[sep_dim] -1) or (box_ll[sep_dim] >= window_ur[sep_dim] +1), "box与window重叠或有公共点"
    
    return box_ll, box_ur

# 3维场景测试示例
if __name__ == "__main__":
    field_ll = np.array([0, 0, 0])
    field_ur = np.array([10, 10, 10])
    window_ll = np.array([3, 3, 3])
    window_ur = np.array([7, 7, 7])
    box_size = np.array([2, 2, 2])
    
    box_ll, box_ur = generate_non_overlapping_box(field_ll, field_ur, window_ll, window_ur, box_size)
    print(f"Box LL: {box_ll}, Box UR: {box_ur}")

关键优势 #

• 高维通用：核心逻辑无需修改即可支持任意维度d≥1
• 鲁棒性强：通过断言提前校验空间可用性，避免无效生成
• 效率高效：仅需处理一个分隔维度，时间复杂度为O(d)

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