泊松圆盘采样（Poisson Disk Sampling）代码实现

欢迎关注更多精彩
关注我，学习常用算法与数据结构，一题多解，降维打击。

参考资料
https://www.jianshu.com/p/4556ccad58d9
https://blog.csdn.net/qq_21476953/article/details/118440245
https://www.bilibili.com/video/av418836005

作用：可以在一个区域内生成均匀的采样点。
性质：做任意2点距离大于r。以每个点为圆作半径为r的圆，这些圆的并集可以基本覆盖到目标区域。

class PoissonDisk {
    typedef pair P;

    bool inCircle(P a, P b, double r) {
        a.first -= b.first;
        a.second -= b.second;
        return a.first*a.first+a.second*a.second< r*r;
    }

    bool isValid(double h, double w, double r,double cellSize,  P newP, vector> &grid, vector
 &points) {
        if(newP.first<0 || newP.first>h || newP.second<0 || newP.second>w) return false; //出界

        // 计算出有可能发生碰撞五乘五格子的上下左右边界
        int up = max(0, int(newP.first/cellSize)-2);
        int down = min(int(grid.size()-1), int(newP.first/cellSize)+2);

        int left = max(0, int(newP.second/cellSize)-2);
        int right = min(int(grid[0].size()-1), int(newP.second/cellSize)+2);

        for(int i=up;i<=down;++i) {
            for(int j=left;j<=right;++j) {
                if(grid[i][j]<0)continue;
                if(inCircle(newP, points[grid[i][j]], r)) return false;
            }
        }

        return true;
    }
public:
    vector
 sampling(double h, double w, double r, int numSamplesBeforeReject=30) {
        srandom(NULL);
        double cellSize = r/sqrt(2);
        vector
 points;
        vector
 spawnPoints;

        vector> grid(ceil(h/cellSize), vector(ceil(w/cellSize),-1)); // 存储格子中是否有生成点，如果有就是大于0，默认-1；

        // 加入一个种子点
        spawnPoints.push_back({h/2, w/2});

        while(!spawnPoints.empty()) {
            bool candidateAccepted = false;
            int spawnIndex = rand()%spawnPoints.size();

            // 每次按种子为中心，从半径r到2r的地带随机选取一点。
            // 并判断是否可行，可行则退出，并加入到候选生成种子，否继续，直到采样次数用完。
            for(int i=0;i
                double angle = rand()%360*1.0/360*2*M_PI;
                // cout<<"pi:"<
                auto dir = P(sin(angle), cos(angle));

                auto newP = spawnPoints[spawnIndex];
                double rl = rand()%1000*1.0/1000*r;
                newP.first+=dir.first*(rl+r);
                newP.second+=dir.second*(rl+r);
                // cout<
                    candidateAccepted = true;
                    grid[newP.first/cellSize][newP.second/cellSize] = points.size();
                    points.push_back(newP);
                    spawnPoints.push_back(newP);
                    break;
                }
            }

            // 采样次数用完，没有得到可行结果，说明该种不可用，直接删除。
            if(!candidateAccepted){
                if(spawnIndex!=spawnPoints.size()-1)
                    spawnPoints[spawnIndex] = spawnPoints[spawnPoints.size()-1];

                spawnPoints.pop_back();
            }
            // cout< 
效果 
 
 
本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。