JavaScript指定范围随机数（排除指定值）及点云生成优化问询

这需求太常见了，我给你几个不同场景下的实用方案，按需选就行：

• 少量排除值：循环重试法
  如果要排除的数值不多（比如两三个），直接用循环生成随机数，直到生成的数不在排除列表里就行，简单粗暴还好用。

  function getRandomInRange(min, max, excluded) {
    let num;
    do {
      // 生成[min, max]范围内的整数随机数
      num = Math.floor(Math.random() * (max - min + 1)) + min;
    } while (excluded.includes(num));
    return num;
  }
  
  // 示例：生成1-10之间的随机数，排除3和7
  console.log(getRandomInRange(1, 10, [3, 7]));
  

  缺点是如果排除的数值占比很高（比如要生成1-100的数，排除90个），可能会多循环几次，但一般小场景完全够用。

• 连续排除区间：拆分范围法
  如果要排除的是连续的一段数值（比如5-8），那直接把原范围拆成两个可用区间，先随机选区间，再在对应区间生成数，完全避免循环。

  function getRandomWithExcludedRange(min, max, excludeMin, excludeMax) {
    const range1Length = excludeMin - min;
    const range2Length = max - excludeMax;
    // 按区间长度加权随机选哪个区间
    const pickRange1 = Math.random() < range1Length / (range1Length + range2Length);
    
    return pickRange1 
      ? Math.floor(Math.random() * range1Length) + min 
      : Math.floor(Math.random() * range2Length) + excludeMax + 1;
  }
  
  // 示例：生成1-10之间的随机数，排除5-8
  console.log(getRandomWithExcludedRange(1, 10, 5, 8));
  

• 大量不连续排除值：预存可用值法
  如果排除的是一堆不连续的数值，而且原范围不大，可以先把所有可用值塞进数组，然后随机选数组索引。

  function getRandomFromAvailable(min, max, excluded) {
    const available = [];
    for (let i = min; i <= max; i++) {
      if (!excluded.includes(i)) available.push(i);
    }
    return available[Math.floor(Math.random() * available.length)];
  }
  

  注意哦，如果原范围特别大（比如1-100000），生成这个数组会占不少内存，这时候还是用循环或者拆分区间更划算。

你原来的思路（每次新增点都遍历所有已有点算距离）确实会随着点数量增加变成O(n²)的复杂度，点多了之后卡得不行。给你两个工业界常用的优化思路，性能提升不是一点半点：

思路一：空间网格划分法 #

核心是把整个空间切成大小固定的网格（网格尺寸设为你要求的最小点间距），每个网格里最多只放一个点。新增点时，只需要检查它所在的网格和相邻的几个网格（2D是9个，3D是27个）里有没有点，不用遍历所有已有点，复杂度直接降到O(1)级别。

给你写个2D场景的实现示例：

class SparsePointCloud {
  constructor(gridSize) {
    this.gridSize = gridSize; // 网格尺寸，建议设为最小点间距
    this.grid = new Map(); // 用`x,y`字符串当键存每个网格里的点
  }

  // 计算点所在的网格键
  #getGridKey(x, y) {
    const gridX = Math.floor(x / this.gridSize);
    const gridY = Math.floor(y / this.gridSize);
    return `${gridX},${gridY}`;
  }

  // 检查点是否符合稀疏要求
  #isPointValid(x, y, minDistance) {
    const [gridX, gridY] = this.#getGridKey(x, y).split(',').map(Number);
    
    // 遍历当前网格及周围8个网格
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const neighborKey = `${gridX + dx},${gridY + dy}`;
        const existingPoint = this.grid.get(neighborKey);
        if (existingPoint) {
          const distance = Math.hypot(x - existingPoint.x, y - existingPoint.y);
          if (distance < minDistance) return false;
        }
      }
    }
    return true;
  }

  // 添加点，成功返回true，失败返回false
  addPoint(x, y, minDistance) {
    if (this.#isPointValid(x, y, minDistance)) {
      this.grid.set(this.#getGridKey(x, y), {x, y});
      return true;
    }
    return false;
  }

  // 批量生成指定数量的点
  generatePoints(targetCount, minX, maxX, minY, maxY, minDistance) {
    const points = [];
    const maxAttempts = targetCount * 10; // 防止无限循环，可根据情况调整
    let attempts = 0;

    while (points.length < targetCount && attempts < maxAttempts) {
      const x = Math.random() * (maxX - minX) + minX;
      const y = Math.random() * (maxY - minY) + minY;
      if (this.addPoint(x, y, minDistance)) {
        points.push({x, y});
      }
      attempts++;
    }
    return points;
  }
}

// 用法示例：生成100个点，范围0-500x0-500，最小间距30
const pointCloud = new SparsePointCloud(30);
const sparsePoints = pointCloud.generatePoints(100, 0, 500, 0, 500, 30);
console.log(sparsePoints);

思路二：泊松圆盘采样法 #

如果你不仅要避免点太密集，还想要点的分布更均匀自然，那泊松圆盘采样绝对是首选。这个算法专门用来生成均匀分布的稀疏点集，核心逻辑是每个点的周围一定范围内不会有其他点，而且采样过程是从已有点向外扩散的，效率很高。

给你一个简化版的2D实现：

function poissonDiskSampling(width, height, minDistance, maxSamplesPerPoint = 30) {
  const gridSize = minDistance / Math.sqrt(2); // 网格尺寸设为最小间距/√2，确保每个网格最多一个点
  // 初始化网格
  const grid = Array.from({length: Math.ceil(width / gridSize)}, () => 
    Array(Math.ceil(height / gridSize)).fill(null)
  );
  const points = [];
  const activePoints = [];

  // 先随机生成第一个点
  const firstPoint = {x: Math.random() * width, y: Math.random() * height};
  points.push(firstPoint);
  activePoints.push(firstPoint);
  const gridX = Math.floor(firstPoint.x / gridSize);
  const gridY = Math.floor(firstPoint.y / gridSize);
  grid[gridX][gridY] = firstPoint;

  while (activePoints.length > 0) {
    const randomIdx = Math.floor(Math.random() * activePoints.length);
    const currentPoint = activePoints[randomIdx];
    let foundNewPoint = false;

    // 尝试在当前点周围生成新点
    for (let i = 0; i < maxSamplesPerPoint; i++) {
      // 在[minDistance, 2*minDistance]范围内随机选方向和距离
      const angle = Math.random() * Math.PI * 2;
      const distance = minDistance + Math.random() * minDistance;
      const newX = currentPoint.x + Math.cos(angle) * distance;
      const newY = currentPoint.y + Math.sin(angle) * distance;

      // 检查是否在边界内
      if (newX < 0 || newX >= width || newY < 0 || newY >= height) continue;

      const newGridX = Math.floor(newX / gridSize);
      const newGridY = Math.floor(newY / gridSize);
      let isValid = true;

      // 检查周围网格有没有点
      for (let dx = -1; dx <= 1; dx++) {
        for (let dy = -1; dy <= 1; dy++) {
          const neighborPoint = grid[newGridX + dx]?.[newGridY + dy];
          if (neighborPoint) {
            const dist = Math.hypot(newX - neighborPoint.x, newY - neighborPoint.y);
            if (dist < minDistance) {
              isValid = false;
              break;
            }
          }
        }
        if (!isValid) break;
      }

      if (isValid) {
        const newPoint = {x: newX, y: newY};
        points.push(newPoint);
        activePoints.push(newPoint);
        grid[newGridX][newGridY] = newPoint;
        foundNewPoint = true;
        break;
      }
    }

    // 如果没找到新点，就从活跃列表里移除当前点
    if (!foundNewPoint) {
      activePoints.splice(randomIdx, 1);
    }
  }

  return points;
}

// 用法示例：生成500x500范围内的泊松分布点，最小间距30
const poissonPoints = poissonDiskSampling(500, 500, 30);
console.log(poissonPoints);

如果是3D点云，思路完全一致，只是网格变成3D的，检查相邻的27个网格即可，泊松采样也能轻松扩展到3D场景。

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