Even distribution of random points in 2D

Question

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. Probably issues with signed values too, but I'm leaving that out for simplicity.

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 no other points in close proximity, or maxPointChecks 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;
            break; // (exit for loop)
        }
        if (tooClose == false){
            // Yay found a point with some space!
            x[newPoint] = testX;
            y[newPoint] = testY;
            break; // (exit do loop)
        }
        //Too close to one of the points, start over.
        pointCheckCount++;
    }
    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?

Answer 1

For the problem you are proposing the best way to generate random samples is to use Poisson Disk Sampling.

https://www.jasondavies.com/poisson-disc

Now if you want to sample random points in a rectangle the simple way. Simply sample two values per point from 0 to the length of the largest dimension.

if the value representing the smaller dimension is larger than the dimension throw the pair away and try again.

Pseudo code:

while (need more points)
begin
   range = max (rect_width, rect_height);

   x = uniform_random(0,range);
   y = uniform_random(0,range);

   if (x > rect_width) or (y > rect_height)
    continue;
   else
     insert point(x,y) into point_list;
end

The reason you sample up to the larger of the two lengths, is to make the uniform selection criteria equivalent when the lengths are different.

For example assume one side is of length K and the other side is of length 10K. And assume the numeric type used has a resolution of 1/1000 of K, then for the shorter side, there are only 1000 possible values, whereas for the longer side there are 10000 possible values to choose from. A probability of 1/1000 is not the same as 1/10000. Simply put the coordinate value for the short side will have a 10x greater probability of occurring than those of the longer side - which means that the sampling is not truly uniform.

---

Pseudo code for the scenario where you want to ensure that the point generated is not closer than some distance to any already generated point:

while (need more points)
begin
   range = max (rect_width, rect_height)

   x = uniform_random(0,range);
   y = uniform_random(0,range);

   if (x > rect_width) or (y > rect_height)
    continue;

   new_point = point(x,y);

   too_close = false;

   for (p : all points)
   begin
     if (distance(p, new_point) < minimum_distance)
     begin
       too_close = true;
       break;
     end
   end

   if (too_close)
      continue;

   insert point(x,y) into point_list;
end