How to generate a random point within a square but NOT within a circle cut out inside the square

Question

Reference Image:

The red circle has a radius of r

The blue square has a side length of s

The goal is to generate a random point within the blue zone but not in the red zone I already have a solution, but it involves trial and error and that is not my prefered method, is there some sort of mathematical solution to this problem?

Here is my method

Let rx and ry be the random variables

rx = random number between 0 and s
ry = random number between 0 and s
while (distance(rx,ry,0,0) < r)
{
   rx = random number between 0 and s
   ry = random number between 0 and s
}
return rx ry;

Answer 1

Ok, why to reject both rx and ry if they are not the ones? Any rx in [-s,s] can be our choice. Therefore;

rx = -s + 2*s*rand();

if(rx<-R || rx>R) % if rx is outside the critical area, you are free on ry
    ry = -s + 2*s*rand();
else % if rx is critical, we are restricted about choosing ry not within [-sqrt(R^2-rx^2),sqrt(R^2-rx^2)]
{
    rand_inst = rand();
    if(rand_inst<0.5) % for the first possible interval [-s, -sqrt(R^2-rx^2)]
        ry = -s + 2*(s-sqrt(R^2-rx^2))*rand_inst;
    else % for the second possible interval [sqrt(R^2-rx^2), s]
        ry = (sqrt(R^2-rx^2) - (s-sqrt(R^2-rx^2)) ) + 2*(s-sqrt(R^2-rx^2))*rand_inst;
}

Answer 2

I'd suggest you stay with the idea you have now, which is formally called rejection sampling and is a relatively common technique for sampling from arbitrary probability distribution using only a uniform random number generator.

The problem of slowdown with an increased number of dimensions is simply unavoidable--this is often called the curse of dimensionality.

While some people have suggested "pushing" points that end up in the circle to points in the acceptable/blue region, it is hard to do this without sacrificing a completely uniform probability distribution. (For example, I could push all points in the circle to the nearest point on the circle's boundary, but this would make the distribution non-uniform as the circle's boundary would be sampled much more often.)

---

To make your code as efficient as possible, you should be calculating (distance(rx,ry,0,0) without calling any functions if possible, and using primative operators likes + and *, rather than any library functions like exp(x,2). In other words, use x*x + y*y < r2 directly in the if statement (with r2 = r*r; predefined somewhere).

Answer 3

I'll not enter on the discussion math vs. programming. For me this question has both. This is my take.

You can try to map a point generated in the [0,1] interval to the blue area. This should give a normal distribution if both shapes were concentric circles. When you have a square, the points will be sparser the closer you get to the diagonal.

The idea is to work in polar coordinates:

1. Assume that the center of your picture is in cartesian (x,y) position (0,0).
2. Generate a number a in the [0,1] interval.
3. Convert this number to an angle w = 2 * pi * a. This will be your polar angle. The equation y = x * tan(w) defines a straight line going through the center of the picture.
4. Now the tricky part: calculate the limits acceptable for the radial part (rho) of the number. It must be larger than the radius of the circle r and smaller than the point where the line defined in step 3 intercepts the square.
5. There will be four possibilities, one for each side of the square. The "top" side is for the case where w has values from pi/4 to 3pi/4; the "left side" is for w ranging from 3pi/4 to 5pi/4; the "bottom side" has w between 5pi/4 and 7pi/4; and the "right" side has w from 7pi/4 to 2pi and from 0 to pi/4.
6. Let's take the top line as an example: it sits at the position y = s / 2. The interception of the line defined in 3 with the top side is then at position s/2 = xi tan(w).
7. The cartesian point (xi, s/2) defines the largest value for rho: R = sqrt(xi^2 + (s/2)^2)
8. Now generate another value b in the [0,1] interval
9. Map this value to the [r,R] interval: rho = r + b * R
10. Finally get your numbers X = rho * cos(w) and Y = rho * sin(w) which should be in the blue area.

Note that from step 5 on, you have to check which side of the square is the one you should take into account (which value of w).

As mentioned above, the problem is that the diagonals are longer than the directions along the main axes producing a sparser distribution. It is up to you to see if that is a problem or not. Note that the mapping does not pile up points close to the circle edge. Also ask yourself if the checks on directions are practical or not (I am assuming that the square and circle shapes are crude approximations to what you really want).

Answer 4

I can see two possibilities. If the circle is a lot smaller than the square, then generate a point inside the square and check if it is inside or outside the circle. If the circle is a large proportion of the square, then find the largest possible radius of the corner of the square furthest from the centre of the circle. Generate a radius that is outside the given circle, but not greater than the distance to the furthest corner. Also generate a theta. If the resulting (r, theta) point is inside the square, then accept it. The method of construction ensures that it is outside the circle.

Answer 5

You could generate two numbers on the range [0..1], and then define a function that maps x for a certain y to a point outside of the circle.

Answer 6

Still, as @Marc stated, technically it's math, not programming. However the answer is to generate a random point and then determine if the length of the line drawn from the center of the square to that point is less than or equal to the radius of the circle. If so, reject it and generate another.