Some math/trig help

[baja_yu]

I need a bit of help. Take a look at the graph below



What I have there is a semi-circle with a 145 radius. Its lowest point on the Y axis is 10, and the highest is 155. On the X axis it spans from 10 to 300.

How would the function to calculate X based on a given Y look like? The result of the calculation would be a pair of values for X, for example for Y = 155 it would be X1 = 10, X2 = 300. The only single point is for Y = 10 where the result is X = 155.

[Nightwalker83]

If this is a serious maths question shouldn't it be moved to the maths form?

[baja_yu]

I didn't know we had a math section. I'll report the thread to be moved.

[baja_yu]

Ok. Here's what I (think I) know:

In a Cartesian coordinate system an equation of a circle with center in point (a,b) with radius r is:

(x-a)^2 + (y-b)^2 = r^2

my center point is (155, 155) and the radius is 145. When I substitute in the values and derive everything down to a quadratic equation (ax^2 + bx + c = 0) I'm left with

x^2 - 310x + (y^2 - 310y + 27025) = 0

The answers to the above nominal equation are

x1 = (-b + sqrt(b^2 - 4ac)) / 2a

and

x2 = (-b - sqrt(b^2 - 4ac)) / 2a

In my case a is 1, b is -310 and c is this whole bunch (y^2 - 310y + 27025).

[gep13]

Moved at OP's request to the Maths Forum.

Gary

[jemidiah]

Post #4 is correct. IMO the final formula is really quite elegant--if you try to put in the "wrong" y values (outside the proper range) you'll take the square root of a negative number. That edge case was implicitly encoded in the circle equation.

[baja_yu]

That's for the reply. Edge cases and outside points wont be a problem. What I'm trying to do is randomly get a point within the half circle area. I'll be generating a random Y value in 11-154 range and based on that I need to calculate a valid X range, in which I'll then again generate a random value.

[jemidiah]

Oh, ok. There are easier ways. Also your distribution with this method will be highly non-uniform, which may or may not be an issue--for instance half of your resulting points will be below the y=82.5 line, while much less than half the area is below that line. [I'm assuming you'd just sample from a uniform distribution with your method and not correct it, since correcting for the non-uniformity requires calculus and most programming languages just include a uniform generator.]

If it were me, I would use rejection sampling. In your case, you would generate (x, y) for x in [10, 300], y in [10, 155]. You would then check to see if these values satisfy (x-a)^2 + (y-b)^2 <= r^2. If so, great--that's your point. If not, pick another (x, y) and keep trying until the values satisfy the equation. This gives a uniform distribution on the semicircle, is very easy to code, and is only a little inefficient in this case. [You'd expect the loop to go through like 4/pi ~= 1.27 iterations.] There are other methods but this is probably the silver bullet.

[baja_yu]

Thanks again for your suggestions. The distribution problem didn't occur to me, though after I implemented this it looks ok (for my purposes at least), I'm generating only about 60-70 points. I've thought about the rejection sampling but I'm doing this on a limited resources device, and I wanted to keep a processing to a minimum by skipping possible 'long' loops.

[jemidiah]

To be clear, the probability that rejection sampling rejects n points in a row is (1 - pi/4)^n. For n=5, this is ~0.046&#37;. The loop will never be "long", for all practical purposes. It might be more efficient (in # of FLOPs) to use your method in the average case--I'd have to count them and it depends on optimization, and even then pipelining could change the efficiency order. But since you've already written your method, I suppose it doesn't matter .