当前位置：首页 > news >正文

泊松圆盘采样进行随机选点

news 2025/6/12 23:32:47

既然要保证点之间的最小距离，那在采样时，就可以以最小距离MinDis为半径画一个圆，在这个圆之外选择候选点。当然为了选择合理，也不能无限范围，通常不会超过2MinDis的范围，实际就变成了在MinDis到2MinDis的一个圆环范围内进行选点，如下图所示的紫色圆盘范围：
在这里插入图片描述
当选中一个候选点时，此时只能保证这个候选点和当前点的距离不小于MinDis，还需要检测其是否跟【已确定点集】中的其他点都满足最小距离要求。为了避免每次都要把所有已有点都遍历计算一遍，我们可以将地图网格化，其实就是空间划分的思路，这样可以快速排除完全不需要比较的点，只对附近的几个格子内的点进行检测即可。

一种标准的划分网格的方式是Bridson算法，以MinDis作为格子的对角线，由于同一个正方形中两个点能够相距的最远距离就是对角线，因此即使在极限情况下，满足距离要求的两个点也不会落到同一个格子中。通过这种方式保证每个格子中最多只有一个点。
在这里插入图片描述
根据勾股定理，此时格子的边长为MinDis / 1.414.

在这种划分下，需要参与检测的最远的情况也就是两个点正好跨了一个格子的对角线，如下图所示。因此在选中候选点后，实际要进行检测的范围只有以该候选点所在格子为中心的5*5的范围内。
在这里插入图片描述

当然，你如果说我就偏不想按照这种方式来划分格子行不行。肯定行。上面也提到过，说白了这个格子就是个空间划分的工具，用来快速筛选目标点的，相当于碰撞检测的BroadPhase阶段，所以只要逻辑合理，怎么划分都可以，只不过不同的划分方式可能带来一些不同的额外情况需要考虑。

这里简单举个例子。比如还是用均匀网格做空间划分，但是我就是想按照MinDis作为格子的边长。这样我就不需要检查5*5的范围，可以把四个角落的格子也排除掉：
在这里插入图片描述

虽然减少了4个候选格子，但是这种划分还会引入其他的额外情况：
在这里插入图片描述
可以看到，紫色圆盘的一部分落在了格子内部，也就是说，在这种划分方式下，同一个格子内可能存在多个点，因此在精确检测的过程中也不能忽略了这点。

（我只是被某些抱着网上答案不会拐弯的人气到了多罗嗦两句而已。。。）

这里还是以MinDis作为对角线的方式进行演示，代码如下：

using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;namespace Client
{public class TestPoisson : MonoBehaviour{public float MapWidth = 100;public float MapHeight = 100;public float MinDistance = 1;public int NumPerRound = 30;private List<Vector2> mFinalPointList = new();private Stack<Vector2> mPrcoessPointStack = new();private int mCellCountX, mCellCountY;private void Update(){if (Input.GetKeyUp(KeyCode.F2)){CreatePoints();}}private void CreatePoints(){mFinalPointList.Clear();mPrcoessPointStack.Clear();float _invCellSize = 1.414f / MinDistance;float _minDisSqr = MinDistance * MinDistance;mCellCountX = Mathf.CeilToInt(MapWidth * _invCellSize);mCellCountY = Mathf.CeilToInt(MapHeight * _invCellSize);Vector2?[,] _cellPoints = new Vector2?[mCellCountX, mCellCountY];Vector2 _firstPoint = new Vector2(Random.value * MapWidth, Random.value * MapHeight);mFinalPointList.Add(_firstPoint);mPrcoessPointStack.Push(_firstPoint);int _firstCellX = (int)(_firstPoint.x * _invCellSize);int _firstCellY = (int)(_firstPoint.y * _invCellSize);_cellPoints[_firstCellX, _firstCellY] = _firstPoint;while (mPrcoessPointStack.Count > 0){Vector2 _point = mPrcoessPointStack.Pop();for (int i = 0; i < NumPerRound; i++){Vector2 _newPoint = GenerateAroundPoint(_point);int _newCellX = (int)(_newPoint.x * _invCellSize);int _newCellY = (int)(_newPoint.y * _invCellSize);if (CheckValid(_newPoint, _minDisSqr, _newCellX, _newCellY, _cellPoints)){mPrcoessPointStack.Push(_newPoint);mFinalPointList.Add(_newPoint);_cellPoints[_newCellX, _newCellY] = _newPoint;}}}}private Vector2 GenerateAroundPoint(Vector2 _originalPoint){float _realRadius = Random.value * MinDistance + MinDistance;float _angleInRad = 2 * Mathf.PI * Random.value;float _x = _originalPoint.x + _realRadius * Mathf.Cos(_angleInRad);float _y = _originalPoint.y + _realRadius * Mathf.Sin(_angleInRad);_x = Mathf.Clamp(_x, 0, MapWidth);_y = Mathf.Clamp(_y, 0, MapHeight);return new Vector2(_x, _y);}private bool CheckValid(Vector2 _checkPoint, float _checkDisSqr, int _cellX, int _cellY, Vector2?[,] _cellPoints){int _startX = Mathf.Max(0, _cellX - 2);int _endX = Mathf.Min(mCellCountX - 1, _cellX + 2);int _startY = Mathf.Max(0, _cellY - 2);int _endY = Mathf.Min(mCellCountY - 1, _cellY + 2);for (int _x = _startX; _x <= _endX; _x++){for (int _y = _startY; _y <= _endY; _y++){if (_cellPoints[_x, _y].HasValue){Vector2 _existPoint = _cellPoints[_x, _y].Value;if (Vector2.SqrMagnitude(_existPoint - _checkPoint) < _checkDisSqr){return false;}}}}return true;}private void OnDrawGizmos(){if (null == mFinalPointList || 0 == mFinalPointList.Count){return;}Gizmos.color = Color.white;foreach (Vector2 _point in mFinalPointList){Gizmos.DrawSphere(_point, 0.1f);}}}
}