How to uniformly spread points in circle shaped form

Question

I've searched through a dozen 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.

enter image description here

Any suggestion would be highly appreciated.

The reason that it's producing more points in the middle is because you're choosing random points along the radius and then changing the angle of the radius. So imagine one of those [radar](http://us.123rf.com/400wm/400/400/happyroman/happyroman1112/happyroman111200731/11486202-vector-radar-screen.jpg) screens with the line moving around. The line moves faster along the outside of the circle than in the center and that's why more points appear in the center. — Mike, Jan 13 '14 at 17:41
This might be helpful http://stackoverflow.com/questions/1621831/how-can-i-convert-coordinates-on-a-square-to-coordinates-on-a-circle — Itay Gal, Jan 13 '14 at 17:43
Is there a specific number of pixels that need to be "on"? Or is it simply based on some probability? — crush, Jan 13 '14 at 17:46
@ItayGal correct me if I'm wrong, but it doesn't look like the distribution is quite uniform in the accepted answer ([link](http://mathproofs.blogspot.com/2005/07/mapping-square-to-circle.html)). The squares near the middle look larger than the ones near the outside, so therefore the outside would have a greater density. — Mike, Jan 13 '14 at 17:48
@crush the number of pixels is the number of points that were added before adding the actualy one. — Eduard, Jan 13 '14 at 17:49
possible duplicate of [Generate a random point within a circle (uniformly)](http://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly) — Mike, Jan 13 '14 at 18:36

lejlot · Accepted Answer · 2014-01-14T15:52:16.307

7

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:

uniformly distributed points on the circle

edited Jan 14 '14 at 15:52

answered Jan 13 '14 at 17:35

lejlot

64,777
8
131
164

1

What if he generated an array of pixels within the circle first. Then, iterated that array each time he was going to spread probability? – crush Jan 13 '14 at 17:38
It won't still be optimal, as you need to iterate through any point of the circle even if you want to place 10 units in it. General approach would be to use the mathematical methods, but as the map is supposed to be just 1000x1000 I think that simple idea which is showed here is better, then the optimal solution (which is less clear). – lejlot Jan 13 '14 at 17:43
I don't really know what about that "random()" in PHP, what should I use in my case, what values is that "random()" supposed to get.. Sorry , but I'm a little bit confused. – Eduard Jan 13 '14 at 17:52
In provided examples I assumed that `random()` is any random number generator from `[0,1]` interval. Obviously in the "mathematical" solution we will have to rescale the whole approach by the circle diameter, proposed method generates random points in circle or radius 1 and center in (0,0). – lejlot Jan 13 '14 at 18:44
Small mistake on the distance formula: Author uses radius when he should use radius squared: if (x-circle_x)^2 + (y-circle_y)^2 <= circle_r^2 – Kieveli Jan 14 '14 at 12:47

score 1 · Answer 2 · answered Jan 13 '14 at 17:52

You could take a random x,y value, then determine if it falls within the circle. If it doesn't, then reject it and try again. When it falls within the circle, then increment your matched hits by one up until you get n random pixels within the circle.

Less math, more calls to random.

How to uniformly spread points in circle shaped form

2 Answers2