formulae / algorithm to select centre cells in a grid?

Question

If I have a grid say consisting of 15 x 15 cells (but variable), what formulae or algorithm would I use to randomly select 20 cells clustered around the centre cell?

I guess I would ideally like to be able to set the centre point, cluster radius, density etc...

any pointers would be really appreciated! cheers.

Answer 1

Randomness within a circle is known paradoxical problem (see Bertrand's paradox). So you need to consider how to randomly distribute the points. Choosing a random distance ranging from 0 to the specified radius, and going in a random direction from the the circle's center (the grid's center) is probably not what you want, since you will have an uneven distribution across the area (more clustering towards the center). I would figure out the AREA of the circle (that is: the cells that are within the circle with the specified radius), maybe store them in a temp array, and choose n (e.g., 20) of them at random. I am not sure that was entirely helpful, but the main idea: DO consider what you mean by random.

Answer 2

monte carlo?

<pseudocode>

found=false
sigma2=3;             // variance
centrex=8; centrey=8; // centre point
while !found
  x=random(15)        //for a 15x15 grid of course!
  y=random(15)
  r2=(x-centrex)^2 + (y-centrey)^2   // squared distance to chosen point
  p=exp(-r2/sigma)                 // probability of accepting this point
  if(p>rand(1)) found=true;        // (calcluated as gaussian distribution)
end

</pseudocode>

You can choose your distribution using the formula on the p= line. here the spread of the distribution can be controlled using the sigma value. For a flat distribution just use p=r2<9 for a radius of 3 for example.

for a gaussian, the radius and density are essentially the same thing, as the integral of p over x and y has to add up to 1.