samedi 4 mars 2017

Even distribution of random points in 2D

I'm trying to do a simple simple 'crowd' model and need distribute random points within a 2D area. This semi-pseudo code is my best attempt, but I can see big issues even before I run it, in that for dense crowds, the chances of a new point being too close could get very high very quickly, making it very inefficient and prone to fail unless the values are fine tuned.

int numPoints = 100;
int x[numPoints];
int y[numPoints];
int testX, testY;

tooCloseRadius = 20;
maxPointChecks = 100;
pointCheckCount = 0;

for (int newPoint = 0; newPoint < numPoints; newPoint++ ){

    //Keep checking random points until one is found with space, or max retries reached.
    while (pointCheckCount < maxPointChecks){
        tooClose = false;
        // Make a new random point and check against all previous points
        testX = random(1000);
        testY = random(1000);
        for ( testPoint = 0; testPoint < newPoint; testPoint++ ){
            if  ( (isTooClose (x[testPoint] , y[testPoint], textX, testY, tooCloseRadius) )  tooClose = true;
        }
        if (tooClose == false){
            // Yay found a point with some space!
            x[newPoint] = testX;
            y[newPoint] = testY;
            break;
        } 
    }
    if (tooClose){
        // maxPointChecks reached without finding a point that has some space.
        // FAILURE DEPARTMENT
    } else {
        // SUCCESS
    }
}

// Simple Trig to check if a point lies within a circle.
(bool) isTooClose(centerX, centerY, testX, testY, testRadius){
    return (testX - centreX)^2 + (testY - centreY)^2)  < testRadius ^2
}

After googling the subject, I believe what I've done is called Rejection Sampling, and the Adaptive Rejection Sampling could be a better approach, but the math is far too complex.

Are there any elegant methods for achieving this that don't require a degree in statistics?




Aucun commentaire:

Enregistrer un commentaire