Uniformly at random distribute n points in a ring (area between 2 circles)

Question

I had looked these topics but they don't resolve my problem:
Uniformly distribute x points inside a circle
Generate a random point within a circle (uniformly)

My problem is:

Randomly distribute n of points between 2 circles.

What I have:

The count of points: n
The center: (x, y)
The radius: r1, r2

Any algorithm to randomly distribute n of points between 2 circles?

Thank you very much!

p/s: I am familiar with C#, C family and pseudo code.

Update This is my attempt. Let's say the center is (0, 0) (for easier looking)

Vector2[] points = new Vector2[n]; 
for (int i = 0; i < n; ++i)
{
    do
    {
        points[n] = new Vector2(Random.Range(0f, r2), Random.Range(0f, r2));
    } while (points[n].magnitude >= r2 || points[n].magnitude <= r1);
}

The general idea would be to generate two random values (x,y) that are within a given range. You can generate random values within a range using: Random rnd = new Random(); int valueBetween1to12 = rnd.Next(1, 13); For the range, you need to do a Cartesian mapping for your circle. — Jazz., Feb 14 '23 at 09:22
[This](https://stackoverflow.com/questions/29060069/random-points-inside-a-circle) should help. Try it yourself and if you are still stuck, SO can help :) — FortyTwo, Feb 14 '23 at 09:23
Randomize a length between r1 and r2 and randomize an angle between 0 and 2Pi. Then translate length,angle into an x,y position. — Ralf, Feb 14 '23 at 09:28
@Ralf This wouldn't give a random distribution of points in the ring. There would be a concentration of points near the centre. — Simon Goater, Feb 14 '23 at 12:38

score 3 · Answer 1 · answered Feb 14 '23 at 09:38

3

Most distribution problems can be solved by rejection sampling. It might not be the fastest technique, but it is easy to implement, and should be fast enough unless you have a large rejection rate. The code it would look something like this:

var center = new Vector(2, 5);
var outerCircle = new Circle2D(center , 6);
var innerCircle = new Circle2D(center , 2);
var bounds = outerCircle.ToBBox2D(); // Get the outer bounds
var rand = new Random(42);
var result = new List<Vector2>();
while (result.Count < 100)
{
    var point = rand.NextVector(bounds); // creates a random point within the bounds
    if (outerCircle.Contains(point) && !innerCircle.Contains(point))
    {
        result.Add(point);
    }
}

This uses some custom types for a circle, box, etc. But I hope the functioning is clear enough.

Note that you may need to be careful with your input parameters. If for example the inner circle would be bigger than the outer circle this would end up in a infinite loop. You might want some additional test that throws an exception after testing a hundred times the number of desired points, or something similar.

There are more elegant/complex techniques for generating random points with some restrictions. But you will have to look for other sources if you want such a solution.

answered Feb 14 '23 at 09:38

JonasH

28,608
2
10
23

1

I upvoted. I would say that the main advantage of this method is that it's easy to prove that it's correct. The drawback of methods that rely on a mathematical formula is that it can be hard to prove that (1) the math is correct; (2) the math was correctly translated into code. In fact, pretty much every stackoverflow question about generating random points have: one answer with a correct rejection method, one answer with a correct mathematical formula, and ten answers with mathematical formula that look correct but are not, and don't give a uniform distribution at all. – Stef Feb 14 '23 at 10:34
@Stef this is exactly like what I'd implemented, so firstly I didn't accept this. But you're right. This actually provide better distribution. – Khang Dinh Hoang Feb 15 '23 at 07:30
@KhangDinhHoang This should provide the same distribution as shingo 's answer, actually. Personally I would have accepted shingo 's answer, which has the correct math formula to produce the correct random distribution directly, more efficiently than the rejection method. – Stef Feb 15 '23 at 09:15
@Stef my bad. I used my own Random implementation, which is more eventually than normal Random (of C#). Under my Random implementation the algorithm (shingo's) distribute more near the center, but for normal Random it look pretty eventually for entire the ring. Thank you very much! – Khang Dinh Hoang Feb 15 '23 at 10:45

score 2 · Accepted Answer · answered Feb 14 '23 at 10:02

2

I had looked these topics but they don't resolve my problem

It doesn't make sense, the answer in the second question should answer this question too. In the Konrad's comment he also provided an algorithm to generate points on a ring.

r1s = r1 * r1
r2s = r2 * r2

r = sqrt(random() * (r2s - r1s) + r1s)
theta = random() * 2 * PI

x = centerX + r * cos(theta)
y = centerY + r * sin(theta)

answered Feb 14 '23 at 10:02

shingo

18,436
5
23
42

This answer has been accepted and this is the same as mine, which has been downvoted :-( No matter, just a remark: I prefer the way I write `r` because it appears as a convex combination of `r1s` and `r2s`. Well, that's just a detail, I know :) – Stéphane Laurent Feb 14 '23 at 13:02
Sir this is not bad but this actually distribute the inner more than the outer. Are there any improved algorithm (based on this?) has more eventually distribution? Thanks. – Khang Dinh Hoang Feb 15 '23 at 07:33
@KhangDinhHoang, can you show your code? The distribution should be even. – shingo Feb 15 '23 at 07:42
@shingo my bad. I used my own Random implementation, which is more eventually than normal Random (of C#), but work with this algorithm wrongly. Seem like I can only use normal Random instead of my implementation. – Khang Dinh Hoang Feb 15 '23 at 10:46

Stéphane Laurent · Answer 3 · 2023-02-14T13:41:14.580

Here is some R code. Say me if you understand it. O is the center of the annulus (ring), n is the desired number of simulations.

runif_in_annulus <- function(n, O, r1, r2){
  theta <- runif(n, 0, 2*pi)
  v <- runif(n)
  r <- sqrt ( ( 1-v ) * r1*r1 + v * r2*r2 )
  cbind(O[1] + r*cos(theta), O[2] + r*sin(theta))
}

I don't remember where I found this method. You could google "uniform sampling annulus".

EDIT

Here is the corresponding pseudo-code. The two numbers r1,r2 are the radii.

  theta = 2*pi*random()
  v     = random()
  r     = sqrt ( (1-v)*r1² + v*r2² )
  return (Ox + r*cos(theta), Oy + r*sin(theta))

Uniformly at random distribute n points in a ring (area between 2 circles)

3 Answers3

EDIT