寻求生成互斥型分散分布随机样本的高效算法

问题背景 #

需要生成样本间存在相互排斥作用的分散分布随机样本（类似Ripley's K算法分析的规则分布，但Ripley's K仅用于分布特性分析）。现有随机采样+距离检查的算法存在明显缺陷：

• 效率极低，样本量增大时每次检查都需遍历所有已有样本
• 为避免死循环逐步减小最小距离阈值，导致大样本时分布趋近于随机分布

现有实现代码（Python）：

for n in range(numSamples):
    tempIdealDistance = idealDistance # 尝试让样本保持的最小距离单位
    newPosition = []
    searchingForLocation = True
    while searchingForLocation:
        # 寻找不与已有样本重叠的位置
        newPosition = [random.randint(lowBounds,highBounds),random.randint(lowBounds,highBounds),random.randint(lowBounds,highBounds)]
        withinRange = False
        for s in samples:
            # 遍历已有样本，检查是否重叠
            existingSamplePosition = np.array(s.GetPos())
            newSamplePosition = np.array(newPosition)
            if np.linalg.norm(existingSamplePosition - newSamplePosition) < tempIdealDistance:
                # 与任意已有样本距离过近，位置无效
                withinRange = True
                break
        if withinRange == False:
            # 新位置符合规则分布要求
            searchingForLocation = False
            samp = Point(newPosition[0],newPosition[1],newPosition[2])
            samp.SetRatio(GetRatio(TiSrB,TiSrA,samp.GetPos(),position),randomNoise)
            samples.append(samp)
        else:
            # 避免无限循环，逐步降低搜索距离
            tempIdealDistance = tempIdealDistance - 1

推荐算法 #

1. 泊松圆盘采样（Poisson Disk Sampling） #

这是生成均匀排斥分布样本的经典算法，核心保证每个样本与其他样本的距离不小于设定的最小阈值，同时维持分布的均匀性。

• 核心优势：
  • 天然满足最小距离要求，无需像现有算法那样逐步降低阈值导致分布退化
  • 效率远高于随机尝试法，尤其适合高维度或大样本场景
  • 支持生成不同密度的分布，可自适应调整参数
• 实现逻辑：
  1. 将空间划分为网格，网格边长设为 最小距离 / sqrt(维度)，确保每个网格最多容纳一个样本
  2. 初始化活跃样本列表，随机生成第一个样本加入列表
  3. 从活跃列表中随机选取一个样本，在其周围 [最小距离, 2*最小距离] 范围内生成候选点
  4. 检查候选点是否在空间边界内，且周围网格无已存在样本，符合条件则加入样本列表和活跃列表
  5. 重复步骤3-4，直到活跃列表为空

2. 网格预分配法 #

适合样本量固定、空间范围已知的场景：

• 实现步骤：
  1. 将目标空间划分为边长等于最小距离的网格
  2. 随机打乱所有网格的顺序
  3. 依次从打乱的网格中选取中心点（或网格内随机点）作为样本，直到达到所需样本量
• 优势：实现简单，保证样本间最小距离不小于网格边长，效率极高
• 局限性：分布随机性稍弱，样本严格落在网格点附近

3. 模拟退火法 #

如果需要生成更灵活的排斥分布（比如非均匀排斥），可以采用模拟退火：

• 核心思路：
  1. 先生成一批随机分布的样本
  2. 定义能量函数，比如所有样本对之间的排斥势能（距离越小势能越高）
  3. 随机移动某个样本，计算能量变化，根据当前退火温度决定是否接受该移动
  4. 逐步降低温度，直到系统稳定
• 优势：支持自定义势能函数，可生成复杂的排斥分布
• 局限性：计算成本较高，适合对分布精度要求高的场景

现有代码的快速优化方案 #

如果暂时不想替换算法，可以通过以下方式提升效率：

• 使用空间索引（如scipy.spatial.KDTree）替代线性遍历，通过query_ball_point方法快速找出距离新样本最近的已有样本，无需遍历全部
• 取消逐步降低tempIdealDistance的逻辑，设置一个最低阈值，当无法找到符合条件的点时直接停止或提示空间不足，避免分布退化
• 预先生成一批候选点，批量检查距离，减少循环次数

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