如何检查随机位置是否在数组已有位置的指定X/Y半径范围内（免全遍历）

你的核心问题是要在避免字母重叠（指定半径内无重复）的同时保证密度，且不遍历整个大数组。直接用数组存坐标字符串并遍历的方式，在数据量大时效率会急剧下降，这里推荐空间网格划分法，通过将画布分割为与最小安全半径匹配的网格，只检查目标点所在网格及相邻网格的点，大幅减少需要检查的数量。

具体实现思路 #

1. 先定义最小安全距离（即你说的半径阈值），比如MIN_DISTANCE = 20，根据你的字母大小调整。
2. 将画布按MIN_DISTANCE为边长分割成网格，这样只有同一个网格或相邻3x3网格内的点，才有可能在安全距离范围内。
3. 用一个grid对象存储每个网格内的所有点，而不是只存所有点的数组，这样查询时只需检查目标点周围的9个网格。
4. 生成随机点后，先计算它所在的网格坐标，再遍历周围网格里的点，计算欧氏距离判断是否在安全范围内。

修改后的代码 #

// 定义最小安全距离（可根据字母大小调整）
const MIN_DISTANCE = 20;
// 存储网格数据，键为网格坐标字符串，值为该网格内的点数组
let grid = {};
// 可选：保留原有的prev数组记录所有点（如果需要后续其他操作）
let prev = [];

function draw() {
  // 生成随机点
  let x = floor(random(width));
  let y = floor(random(height));
  
  // 计算当前点所在的网格坐标
  let gridX = floor(x / MIN_DISTANCE);
  let gridY = floor(y / MIN_DISTANCE);
  
  // 标记是否可以放置当前点
  let canPlace = true;
  
  // 检查周围3x3的网格（只有这些网格里的点才可能在安全距离内）
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      let checkGridKey = `${gridX + dx}:${gridY + dy}`;
      // 如果该网格存在点，逐个计算距离
      if (grid[checkGridKey]) {
        for (let [px, py] of grid[checkGridKey]) {
          let distance = dist(x, y, px, py);
          if (distance < MIN_DISTANCE) {
            canPlace = false;
            break; // 找到冲突点，跳出循环
          }
        }
        if (!canPlace) break;
      }
    }
    if (!canPlace) break;
  }
  
  // 如果可以放置，执行绘制并记录
  if (canPlace) {
    let col = img.get(x, y);
    fill(red(col), green(col), blue(col));
    text('E', x, y);
    
    // 记录到prev数组（如果需要）
    prev.push(`${x}:${y}`);
    
    // 记录到网格中
    let currentGridKey = `${gridX}:${gridY}`;
    if (!grid[currentGridKey]) {
      grid[currentGridKey] = [];
    }
    grid[currentGridKey].push([x, y]);
  }
}

关键优化点 #

• 避免了遍历整个prev数组，只检查目标点周围最多9个网格内的点，数据量越大，效率提升越明显。
• 用网格划分缩小了查询范围，本质是用空间换时间，属于常见的碰撞检测优化手段。
• 保留了原有的prev数组，如果后续需要全局遍历所有点，依然可以使用。

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