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

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 2

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.