如何以圆形形式均匀地传播点

Question

I've searched through a dosen of questions similar to this one, but none with the same problem I've came upon. I have a map with units, 1000x1000 units, think of it as pixels. The problem is that I have to uniformly spread circle-shaped into the 1000x1000 map and all I could come up with till now is this:

$quadrant = array_search(min($quadrants), $quadrants); // the quadrant with less points
$radius = (current_points_number / sqrt(pi() / $points_density);
$angle = pi() * mt_rand() / 2 / mt_getrandmax();
$x = round((($quadrant == 2 || $quadrant == 3) ? -1 : 1) * cos($angle) * $radius + 500);
$y = round((($quadrant == 3 || $quadrant == 4) ? -1 : 1) * sin($angle) * $radius + 500);

The result of this actual algorithm is , as you can see in the next image, a problem, since it tends to make points denser to the center of the circle and widely scattered on at it's margins.

Any suggestion would be highly appreciated.

Answer 1

simple solution

you can simply iterate through all map's pixels, and for each pixel inside of the given circle - create unit with probability P``, so the code is something like

for x=1 to max_x
  for y=1 to max_y
    if (x-circle_x)^2 + (y-circle_y)^2 <= circle_r^2
      if random() < P
        map[x][y] = new unit()     

Obviously it is not optimal, as you do not really need iteration through non-circle points, but this should give you the general idea. It is easy to prove, that it generates the uniform distribution, as it is simply generation of the uniform distribution on the whole map and "removing" units from outside of the circle.

more mathematical solution

You can also do it in more strict way, by applying iteratively the uniformly distributed points generator:

for i in 1...numer_of_units_to_generate:
  t = 2*pi*random()
  u = random()+random()
  if u>1 then 
    r=2-u 
  else 
    r=u
  map[r*cos(t)][r*sin(t)]=new unit()

result: