Three.js无重叠随机网格放置：如何实现平面无重叠随机圆形布局？

Hey there! 我来给你分享几个在Three.js场景里基于X、Y坐标随机放置圆形且不重叠的靠谱方案，都是实际项目里验证过的思路，你可以根据自己的需求选：

这是最直观的方法，适合圆形数量不多（比如几十上百个）的场景。核心逻辑就是：每次生成一个新的随机位置后，和所有已经放置好的圆形做距离检测——如果新位置和所有已有圆形的中心距离都大于两个圆形半径之和，就保留这个位置；否则重新生成，直到找到符合条件的位置。

举个Three.js的代码示例：

const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(75, window.innerWidth/window.innerHeight, 0.1, 1000);
const renderer = new THREE.WebGLRenderer();
renderer.setSize(window.innerWidth, window.innerHeight);
document.body.appendChild(renderer.domElement);

const circleRadius = 1; // 假设所有圆形半径相同
const maxAttempts = 1000; // 防止无限循环的最大尝试次数
const placedCircles = []; // 存储已放置圆形的中心坐标
const totalCircles = 50; // 要生成的圆形总数

for (let i = 0; i < totalCircles; i++) {
  let isValidPosition = false;
  let newX, newY;
  let attempts = 0;

  // 循环尝试生成有效位置
  while (!isValidPosition && attempts < maxAttempts) {
    attempts++;
    // 在指定范围内生成随机X、Y坐标（这里是-10到10的区间）
    newX = THREE.MathUtils.randFloat(-10, 10);
    newY = THREE.MathUtils.randFloat(-10, 10);

    // 检测是否和已有圆形重叠
    isValidPosition = placedCircles.every(([x, y]) => {
      const distance = Math.sqrt(Math.pow(newX - x, 2) + Math.pow(newY - y, 2));
      return distance > circleRadius * 2; // 两个半径之和
    });
  }

  if (isValidPosition) {
    // 创建圆形Mesh
    const geometry = new THREE.CircleBufferGeometry(circleRadius, 32);
    const material = new THREE.MeshBasicMaterial({ color: 0x00ff00 });
    const circle = new THREE.Mesh(geometry, material);
    circle.position.set(newX, newY, 0); // Z轴设为0，放在XY平面
    scene.add(circle);
    placedCircles.push([newX, newY]);
  } else {
    console.warn(`第${i+1}个圆形无法找到有效位置，已跳过`);
  }
}

camera.position.z = 20;
function animate() {
  requestAnimationFrame(animate);
  renderer.render(scene, camera);
}
animate();

如果你的圆形半径不一样，只需要把检测条件改成distance > circleRadius + newCircleRadius就行，记得把每个圆形的半径也存在placedCircles数组里。

当圆形数量上千的时候，暴力检测会变得很慢——毕竟每生成一个新圆形都要和所有已有圆形对比。这时候可以用空间网格分区来减少检测次数：

1. 把XY平面划分成一个个网格单元，每个单元的边长等于你要放置的圆形的最大半径（如果半径统一，就等于半径）。
2. 每个网格单元里最多只能放一个圆形，这样生成新位置时，只需要检测它所在网格以及相邻的8个网格里的圆形，不用遍历所有已放置的圆形。

代码示例（基于上面的基础修改）：

const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(75, window.innerWidth/window.innerHeight, 0.1, 1000);
const renderer = new THREE.WebGLRenderer();
renderer.setSize(window.innerWidth, window.innerHeight);
document.body.appendChild(renderer.domElement);

const circleRadius = 1;
const gridCellSize = circleRadius; // 网格单元边长等于半径
const grid = new Map(); // 用Map存储网格单元和对应的圆形中心坐标
const totalCircles = 200;
const maxAttempts = 1000;
const areaRange = [-15, 15]; // 放置范围：x和y从-15到15

// 获取某个坐标对应的网格键
function getGridKey(x, y) {
  const gridX = Math.floor(x / gridCellSize);
  const gridY = Math.floor(y / gridCellSize);
  return `${gridX},${gridY}`;
}

// 检测相邻网格内的圆形是否重叠
function isPositionValid(x, y) {
  const gridKey = getGridKey(x, y);
  // 检查当前网格和周围8个网格
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      const neighborKey = `${parseInt(gridKey.split(',')[0]) + dx},${parseInt(gridKey.split(',')[1]) + dy}`;
      const neighborPos = grid.get(neighborKey);
      if (neighborPos) {
        const distance = Math.sqrt(Math.pow(x - neighborPos[0], 2) + Math.pow(y - neighborPos[1], 2));
        if (distance <= circleRadius * 2) {
          return false;
        }
      }
    }
  }
  return true;
}

for (let i = 0; i < totalCircles; i++) {
  let isValidPosition = false;
  let newX, newY;
  let attempts = 0;

  while (!isValidPosition && attempts < maxAttempts) {
    attempts++;
    newX = THREE.MathUtils.randFloat(areaRange[0], areaRange[1]);
    newY = THREE.MathUtils.randFloat(areaRange[0], areaRange[1]);
    isValidPosition = isPositionValid(newX, newY);
  }

  if (isValidPosition) {
    const geometry = new THREE.CircleBufferGeometry(circleRadius, 32);
    const material = new THREE.MeshBasicMaterial({ color: 0x00ff00 });
    const circle = new THREE.Mesh(geometry, material);
    circle.position.set(newX, newY, 0);
    scene.add(circle);
    grid.set(getGridKey(newX, newY), [newX, newY]);
  } else {
    console.warn(`第${i+1}个圆形无法找到有效位置，已跳过`);
  }
}

camera.position.z = 30;
function animate() {
  requestAnimationFrame(animate);
  renderer.render(scene, camera);
}
animate();

这个方法能把检测的时间复杂度从O(n²)降到接近O(n)，数量多的时候性能提升很明显。

如果你想要生成的圆形分布更均匀，不会出现“扎堆”或者“稀疏不均”的情况，那Poisson圆盘采样是绝佳选择——它能保证每个点（圆形中心）和其他所有点的距离都大于设定的最小间距（也就是两个半径之和），同时分布更贴近自然随机的效果。

核心思路是用一个采样算法生成符合要求的点集，再把这些点转换成Three.js的圆形。这里给你一个简化版的实现：

const scene = new THREE.Scene();
const camera = new THREE.PerspectiveCamera(75, window.innerWidth/window.innerHeight, 0.1, 1000);
const renderer = new THREE.WebGLRenderer();
renderer.setSize(window.innerWidth, window.innerHeight);
document.body.appendChild(renderer.domElement);

const circleRadius = 1;
const minDistance = circleRadius * 2; // 最小间距，等于两个半径之和
const areaRange = { x: [-15, 15], y: [-15, 15] };
const totalSamples = 150;
const gridCellSize = minDistance / Math.sqrt(2); // 网格单元边长优化，减少无效检测

// 实现Poisson圆盘采样
function poissonDiskSampling() {
  const grid = new Map();
  const samples = [];
  const activeList = [];

  // 生成第一个随机点
  const firstX = THREE.MathUtils.randFloat(areaRange.x[0], areaRange.x[1]);
  const firstY = THREE.MathUtils.randFloat(areaRange.y[0], areaRange.y[1]);
  const firstSample = [firstX, firstY];
  samples.push(firstSample);
  activeList.push(firstSample);
  grid.set(getGridKey(firstX, firstY), firstSample);

  while (activeList.length > 0 && samples.length < totalSamples) {
    const randomIndex = Math.floor(Math.random() * activeList.length);
    const currentSample = activeList[randomIndex];
    let foundValid = false;

    // 尝试生成10个候选点（可调整数量，越多越容易找到有效点）
    for (let i = 0; i < 10; i++) {
      // 在minDistance到2*minDistance的范围内生成随机方向的点
      const angle = Math.random() * Math.PI * 2;
      const distance = minDistance + Math.random() * minDistance;
      const newX = currentSample[0] + Math.cos(angle) * distance;
      const newY = currentSample[1] + Math.sin(angle) * distance;

      // 检查是否在范围内，且和已有样本间距足够
      if (newX >= areaRange.x[0] && newX <= areaRange.x[1] &&
          newY >= areaRange.y[0] && newY <= areaRange.y[1] &&
          isSampleValid(newX, newY, grid, minDistance)) {
        const newSample = [newX, newY];
        samples.push(newSample);
        activeList.push(newSample);
        grid.set(getGridKey(newX, newY), newSample);
        foundValid = true;
        break;
      }
    }

    // 如果没找到有效点，从活跃列表移除当前样本
    if (!foundValid) {
      activeList.splice(randomIndex, 1);
    }
  }

  return samples;
}

function getGridKey(x, y) {
  const gridX = Math.floor(x / gridCellSize);
  const gridY = Math.floor(y / gridCellSize);
  return `${gridX},${gridY}`;
}

function isSampleValid(x, y, grid, minDistance) {
  const gridKey = getGridKey(x, y);
  // 检查周围9个网格
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      const neighborKey = `${parseInt(gridKey.split(',')[0]) + dx},${parseInt(gridKey.split(',')[1]) + dy}`;
      const neighborSample = grid.get(neighborKey);
      if (neighborSample) {
        const distance = Math.sqrt(Math.pow(x - neighborSample[0], 2) + Math.pow(y - neighborSample[1], 2));
        if (distance < minDistance) {
          return false;
        }
      }
    }
  }
  return true;
}

// 生成采样点并创建圆形
const samples = poissonDiskSampling();
samples.forEach(([x, y]) => {
  const geometry = new THREE.CircleBufferGeometry(circleRadius, 32);
  const material = new THREE.MeshBasicMaterial({ color: 0x00ff00 });
  const circle = new THREE.Mesh(geometry, material);
  circle.position.set(x, y, 0);
  scene.add(circle);
});

camera.position.z = 30;
function animate() {
  requestAnimationFrame(animate);
  renderer.render(scene, camera);
}
animate();

这个方法生成的圆形分布会非常均匀，视觉体验更好，适合需要美观布局的场景。

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