Coding Challenge/Help me [Random point in square with circle cut out] [Come try]

[Swollow]

For all intensive purposes assume the red circle is directly in the middle of the square

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
however I would like to see anyone's pseudocode regardless of the method
we can crown the winner of the most efficient method

[Ad Bot]

[Greek2me]

I wrote a nice informal solution for you:

[Val]

It's easy enough to pick a random location on the side of the circle, it's just the hard part is "stretching" the bounds around the corners of the square based on theta. Try figuring something out for that. It reminds me of when I used polar coordinates to make shadows in glsl. The math was horrifying, so good luck.

But on that note: considering the solutions will be using a heap of function calls anyways, I think your rejection sampling is good enough for the average case, performance-wise.

[boodals 2]

Probably the easiest method is just to generate a random point within the square, then if its within the circle, pick another point and try again..

Code: [Select]

while(1) {
  %x = getRandom() * %s - %s / 2;
  %y = getRandom() * %s - %s / 2;

  if(vectorLen(%x SPC %y) >= %r)
    return %x SPC %y;
}
However, that could take many iterations if the radius is big.

[Greek2me]

It's easy enough to pick a random location on the side of the circle, it's just the hard part is "stretching" the bounds around the corners of the square based on theta. Try figuring something out for that. It reminds me of when I used polar coordinates to make shadows in glsl. The math was horrifying, so good luck.

But on that note: considering the solutions will be using a heap of function calls anyways, I think your rejection sampling is good enough for the average case, performance-wise.

This is essentially what I did above. It's the best solution because the math is very easy for the computer to do and it only takes one try. (no guess-and-check)

edit: Not the best solution because something doesn't work yet...

[Ipquarx]

The problem with the solution greek and val posted is that they more than likely won't be uniformly distributed, and they'll have a bias towards certain areas and against others.

However if you don't care about that then it's a perfectly fine solution.

[phflack]

if it's based on a grid of pixels

Code: [Select]

function getPossibleSpots(int s, int r) //find the pixels in 1/4 of square - circle, multiply by 4 and return
{
s = s / 2;
int area = s * s - s * r; //the vertical buffer room
int rr = r * r;
for(int i = 0; i < r; i++)
area += s - (int)Math.sqrt(rr - i * i);
return area * 4;
}

function decodeSpot(int s, int r, int spot)
{
s = s / 2;
int quadrant = spot % 4;
spot = spot >> 2;
int y = 0;
int rr = r * r;
for(int i = 0; i < s - r; i++)
if(spot < s)
return rotateSpot(s * 2, r, spot, y, quadrant);
else
{
spot -= s;
y++;
}
for(int i = r; i >= 0; i--)
if(spot < (int)Math.sqrt(rr - i * i))
return rotateSpot(s * 2, r, spot, y, quadrant);
else
{
spot -= (int)Math.sqrt(rr - i * i));
y++;
}
return rotateSpot(s * 2, r, spot, y, quadrant);
}

function rotateSpot(int s, int r, int x, int y, int quadrant)
{
if(quadrant | 1)
x = s - x;
if(quadrant | 2)
y = s - y;
return x SPC y;
}

function getRandomSpot(int s, int r)
{
return decodeSpot(s, r, (int)(Math.random() * getPossibleSpots(s, r)));
}

something like that could work

it's kind of terrible, but should be a uniform distribution

[Klarck]

my solution in pseudocode
Note: not uniform distribution but not extremely biased so its probably good enough for your usage.
(i might try and find a uniform solution later on)
currently biased towards the areas the circle is closer to the square.

Code: [Select]

function randomSpot(r, s)
{
    t = getrandom(-pi, pi)
    m = 0
    if((|t| > pi / 4) and (|t| < pi * 3 / 4))
        m = 1 / sin(t)
    else
        m = 1 / cos(t)

    m = |m|;
    m = getrandom(0, 1) * (m * (s / 2) - r) + r
    return (cos(t) * m, sin(t) * m)
}
EDIT: if you are working on the GPU which doesnt like branching you could replace

Code: [Select]

if((|t| > pi / 4) and (|t| < pi * 3 / 4))
        m = 1 / sin(t)
    else
        m = 1 / cos(t)
with

Code: [Select]

m = min(1 / sin(t), 1 / cos(t))


[Alphadin]

Assuming the origin of the square is in the top left and the box itself is at 0,0
Assuming every rand# is a number inclusive of 0 and exclusive of 1

truelength = side / 2
x = rand# * truelength
y = rand# * truelength
rad = atan2(y - truelength, x - truelength) - Get what direction the point it from the center of the circle
if(x > cos(degree) * radius && y > sin(degree) * radius) - This would classify as in the circle
x -= radius
y -=  radius
turnRad = floor(rand# * 4)
turnRad *= 90
turnRad *= (pi / 180)
x = ((x - (x origin + truelength)) * cos(turnRad)) - (((y origin + truelength) - y) * sin(turnRad)) + (x origin + truelength)
y = (((y origin + truelength) - y) * cos(turnRad)) - ((x - (x origin + truelength)) * sin(turnRad)) + (y origin + truelength) - super complex (not really) vector turning.

Basically what I tried to do (0 Idea if it would work it's completely hypothetical) was to use only the top left corner to help simplify math. It checks if the position is inside of the circle, and if it is, it subtracts the radius of the circle to pull it away. After that, since I know the position is already legal for the top left corner, I can just rotate the entire thing by any increment of 90 degrees from the center of the circle and still have a legal position. This solution would/should generally leave more points in a circular pattern than not.

EDIT:
I'm doing test runs in Java and most if not all that math is actually forgeted up zzz.

EDIT2:
Assuming Center of Box is 0,0


For my solution I only use quadrant 1 (+,+). It checks if the position is inside of the circle, and if it is, it subtracts the radius of the circle to pull it away. After that, since I know the position is already legal for the top right corner, I can just rotate the entire thing by any increment of 90 degrees from the center of the circle and still have a legal position. This solution generally leaves more points in a circular pattern than not.

[Klarck]

-snip-

yea thats kind of wrong

from what i can see, you are doing several things incorrectly:

• when you are checking if the point is inside the circle you are actually checking if its outside the circle, and you are overcomplicating it when you could just use {sqrt(x*x+y*y) < r}
• when you do the vector rotation you are using the new value of x as the previous value of x when evaluating y. you could greatly simplify this by just changing the sign of X and Y randomly. (assuming the origin is at 0,0)
• you could simplify the turnRad evaluation to {turnRad *= pi / 2}

[Alphadin]

-snip-

I resolved those problems (Save for the last one) with the revision from inside of actual Java.

[Klarck]

im not sure if your method will work since from what i understood you are pushing every point inside the circle out of it. this can fail in case of r > s / 4 (try it for yourself). the resulting pushed points can lay outside of the square. also your method is really biased, where there will be twice as many points within 2r from the origin than outside of that.

[Klarck]

btw my method is based off of this:

basically 1/sin(t) forms a line
if you take the absolute value of that it forms two parallel lines
if you use 1/cos(t) you get the same lines rotated by 90 degrees
and if you take the minimum of both you only get the square intersection of them.

[phflack]

so many doubles make me go ew
since normally with BL you'd be working with "pixels", either for a GUI or for bricks ingame

[Alphadin]

so many doubles make me go ew
since normally with BL you'd be working with "pixels", either for a GUI or for bricks ingame

Yeah I didn't feel like concverting my numbers around