# How to efficiently generate random points in a difference of two disks?

Consider two disks: $$S$$ with radius $$R_S$$ and position $$(x_S,y_S)$$, and $$M$$ with radius $$R_M$$ and position $$(x_M,y_M)$$. Let's denote the difference between these two sets as

$$V=S\setminus M.$$

Now the problem is: given two uniformly distributed random numbers $$a,b\in[0,1]$$, assuming $$V\ne\emptyset$$, compose from them a uniformly distributed point $$p=(x,y)\in V$$.

The most obvious solution would be to generate a point $$p_0=f(a,b)\in S$$ (where $$f$$ is simple to construct) and, if $$p_0\in M$$, then discard it, otherwise return $$p_0$$. But for large overlaps between $$S$$ and $$M$$ (e.g. solar eclipse just before totality, with $$S$$ being the Sun and $$M$$ the Moon) this strategy will be grossly inefficient due to high rejection rate.

A better approach is to find the thinnest annulus $$A$$ with outer radius being $$R_S$$ and inner radius just small enough to fit $$V$$ into $$A$$. If we sample only inside the annulus (which is a simple modification of sampling in a full disk), we'll drastically reduce the rejection rate.

But this is still not the best. I suppose there should be a simple way to generate random points in $$V$$ without rejection at all. But I can't seem to find a way. How can this be done?

With rejection, a simple improvement might be the following: assume WLOG that $$y_S=y_M$$ , $$x_S-R_S < x_M-R_M$$, so that one has the zone depicted in the figure. Let $$h$$ be the height of the smallest containing rectangle, let $$t= (x_M-R_M) - (x_S-R_S)>0$$.
Then, first map the square to a rectangle $$a' = a t$$ , $$b'=b h$$ . In this way, we get uniform points inside the green rectangle. Then shift $$a'$$ to the right so that it gets inside the red circle (arrows). If the resulting point is outside the $$V$$, discard and retry. It would be possible to do something similar without rejection, but it looks quite cumbersome. Now we would shift and scale $$a'$$, so that it always get into $$V$$. But then, $$b'$$ should have been remapped so that its probability density is not uniform but proportional to the lentgh of the corresponding horizontal segment inside $$V$$.