circle & vector geometry/trig problem

Are the blue and red lines parallel lines?

If so, find the equation for the red line, then translate that line to the blue lines position. This will allow you to find the point of B I believe.

Hi,

Blue and red lines are parallel.

You know two points for the red line, so you can determine m, b the equation of the line: mx + b = y.

Given m, you may construct a line that passes through A.

Intersect this line with the equation of the circle (x^2 + y^2 = 10^2), you'll have two solutions, pick the one with y<6 or x<4.5.

Having the point A, you can easily obtain the length of the blue line.

siranm,

I am not clear on your solution with how to intersect a line created with mx + b = y with the circle equation.

I see how to create the line that passes through A.  I do not see how that helps me find either the x or y component of B to plug into the circle equation to determine the other component.

x^2 + y^2 = 10^2

x = (10^2 - y^2)^1/2

Since mx + b = y,

x = (y-b)/m = (10^2 - y^2)^1/2

You arrive to what is called a "trascendent equation", which needs to be solved numerically (matlab, mathematica would help).

Maybe there is some property i'm missing which makes the solution simpler.

>>Maybe there is some property i'm missing which makes the solution simpler

That's what I am thinking.

What about using Trig since the angle of the red line can be found. Splitting everything up into right triangles? Does that sound plausible? Seems like a hard way around though.

Anybody else??

In your case two equations, two unknowns. No need for trig or triangles.
y = m*x + b
x^2 + y^2 = r^2
Find m for red   (b = 0)        m = -7/(-20) = 7/20
Now consider A. You know x,y ie -4.5,6 and m so find eq for blue
Blue:    y = (7/20)*x +b    put in x = -4.5 and y = 6    get b = 7.575
You now have
Blue:    y = (7/20)*x + 7.575       one
Circle      x^2 + y^2 = 100          two
Square one, put into two    solve for x  (since x is square you get two values, one in 4 quadrant (the one you want), one in 1 quadrant (discard))
Having found x put into one or two to get y
QED   (except you used no geometry)

the length of the blue line segment should be
sqrt(r**2-(-7*-4.5 - -20*6)**2/(-7*-7 + -20*-20)) - (-20*-4.5 + -7*6)/sqrt(-7*-7 + -20*-20)

Another way to look at this, is:

You know that the blue vector is a linear multiple of the red vector, or:

  v = (-20m, -7m)

Let r  be the vector r(-4.5,6), you now know that r + v = b.

You also know that b_x^2 + b_y^2 = 100.

-4.5 - 20m = b_x
6 - 7m = b_y

b_x^2 + b_y^2 = 100

You should be able to solve this quadratic equation and determine the multiple m of the red vector, from that you should be able to determine the vector B.

Ok, there is NO trascendent equation, see what I got:

from the circle equation I get x:
x^2 + y^2 = 10^2
x = (10^2 - y^2)^1/2

Since mx + b = y, (given m,b to match the blue line)

From the line equation I get x
x = (y-b)/m = (10^2 - y^2)^1/2

I equate both x's:
(y-b)/m = (10^2 - y^2)^1/2

squaring both sides:
(y-b)^2 = m^2*(10^2 - y^2)

y^2 -2by + b^2 = (10m)^2 - (my)^2

Putting all on the same side:
y^2(m^2+1)-y(2b) + b^2-(10m)^2 = 0

= Ay^2 + By + C

where, A = m^2+1, B=-2b, C=b^2-(10m)^2

Theres a quadratic equation you should be able to solve....

Really showing my lack of math skills here,

aburr,
following through, I come up with: x^2 + (0.35x + 7.757)^2 - 100 = 0

I'm not sure how to get x alone on one side. sorry, I'm 25 years out of school. If you don't mind, please give me another push towards the coordinates of B.

ozo,
I may getting fouled up in the associative/commutative/distributive...ness of it. to solve for these parenthesis group, (-7*-4.5--20*6),, would I go left to right or should I do something like this: ((-7*-4.5)-(-20*6))? Do you end up with -3.67? That's what I got adding the extra parens and it does sound reasonable.

BrianGEFF719,
again I get to (-4.5 - 20m)^2 + (6-7m)^2 = 100 and find I need help to reduce/factor or whatever its called to solve for m. Are you saying that m will be the length of the blue vector?

siranm,
 
thanks, i'll study your post now.

the slope "m" of the red line

m= (y2-y1)/(x2-x1) = (-7 - 0)/(-20-0) = -7/-20 = 7/20

Next, we obtain "b" for the line passing through A, having the slope "m"

from the line equation:

mx + b = y

m*(-4.5) + b = 6

b = 6 + 4.5m = a number

So we have the *numerical values* of "m" and "b":

m=7/20
b=6 + 4.5*7/20

Next, you solve the quadratic equation from my previous post using:

http://upload.wikimedia.org/math/3/e/a/3ea647783b5121989cd87ca3bb558916.png

http://en.wikipedia.org/wiki/Quadratic_equation

http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula

OK siramn, I think I'm a little farther along now. but only a little...

using m = 7/20 = 0.35
b= 6.45 + 4.5m = 3.68

and

A = m^2+1, B=-2b, C=b^2-(10m)^2

plugging that into  http://upload.wikimedia.org/math/3/e/a/3ea647783b5121989cd87ca3bb558916.png

and substituting A, B, C for a, b, c

I get a result of 3.49 if I use the +
Or 1.96 if I use the -

Does that mean that the x component of point B on my sketch is 3.49? or is that the distance between point A & B?? or if neither, then what do they mean relevant to either point B or the distance from A to B.

if you let C be the intersection between the line through AB and the line through (0,0) that is perpendicular to the line through (-20,-7) then the length of BC is ((-20*-4.5) + (-7*6))/sqrt((-7*-7) + (-20*-20))
the length of 0C is ((-7*-4.5) - (-20*6))/sqrt((-7*-7 )+ (-20*-20))
and the length of AC is sqrt(r**2-((-7*-4.5) - (-20*6))**2/((-7*-7 )+ (-20*-20)))

Sorry'
the length of AC is ((-20*-4.5) + (-7*6))/sqrt((-7*-7) + (-20*-20))
and the length of BC is sqrt(r**2-((-7*-4.5) - (-20*6))**2/((-7*-7 )+ (-20*-20)))

ozo,

if I understand you correctly (see updated sketch), AB length = BC - AC = 4.86... sounds about right. I'll test it with a few different points & red vectors.

Will this formula work (plugging in appropriate values) no matter where point A is as long as it's inside the circle?
penetrationDistance.jpg

I'll try and figure it out when A is on the other side of the perp. If I have trouble with that I'll ask.

hi,

<<
using m = 7/20 = 0.35
b= 6.45 + 4.5m = 3.68
>>

you calculated b incorrectly,

b = 6.45 + (4.5*7/20) = 6.45 + 1.575 = 8.025 !!

>>again I get to (-4.5 - 20m)^2 + (6-7m)^2 = 100 and find I need help to reduce/factor or whatever its called to solve for m. Are you saying that m will be the length of the blue vector?

No, m is the linear multiple of the red vector, m will 'define' the blue vector as m * red vector, and then you can add the blue vector plus the r-vector (-4.5,6) to get the point B.

Make sense?

> Will this formula work (plugging in appropriate values) no matter where point A is as long as it's inside the circle?
It will work even if A is outside the circle, but if C is outside the circle, you can get the square root of a negative number,

Hi, I redid the calculations....

The correct answer is:

bx=      -8,96
by=      4,44

distance AB=      4,73

I'll attach the .XLS where I did the numeric calculations... The logic is what I told, I only had missed a factor...

m=7/20
b=4.5m+6

(a) x^2+y^2=10^2

(b) mx+b=y

Introducing (b) in eq (a),

x^2 + (mx+b)^2 = 10^2

Expanding the square and putting all terms on the left side,

x^2 + m^2*x^2 + +b^2 + 2mbx - 10^2 = 0

grouping by powers of x,

(1+m^2)*x^2 + (2*m*b)*x + (b^2-10^2) = 0

Ax^2 + Bx + C = 0

where A = 1+m^2, B=2mb, C=b^2-10^2

Now I use the attached .XLS for the numeric calculations (using http://upload.wikimedia.org/math/3/e/a/3ea647783b5121989cd87ca3bb558916.png)

voilà!











circle---vector-geometry.xls

Let A = (-4.5, 6), C = (-20, -7).   We want to find B, which is in line with A, in the direction of C, and at a distance of 10 from the origin.

B = A + alpha * C
|B| = 10
(B.x, B.y)  = (A.x, A.y) + alpha * (C.x, C.y)
B.x^2 + B.y^2 = 100
(A.x + alpha * C.x)^2 + (A.y + alpha*C.y)^2 = 100
alpha^2 * (C.x^2 + C.y^2) + alpha * 2 * (A.x * C.x + A.y * C.y) + (A.x^2 + A.y^2) = 100
Now we can use an exotic solution method called "the quadratic equation" to solve for alpha.
There may be zero, one, or two solutions for alpha.  The one you want depends on what you can assume about A and C and their orientation to the circle, and where you want B to be.

ah-hem.

PLEASE STOP USING SLOPE WHEN YOU SHOULD BE USING 2-D LINEAR ALGEBRA

How are you dealing with vertical lines?  Are you just ignoring them?  Assuming they will never happen?

I know you all learned the slope-intersect formula in middle school.  That doesn't mean you should use it.  When you're dealing with well-behaved continuous functions, it's ok because you're guaranteed not to have any vertical lines.  But when you're dealing with 2-d geometry like this, it's just stupid.  Use 2-d linear algebra, and you will find that this sort of thing becomes much simpler.

Nova, I pointed that out many comments ago but for some reason no one listened :/

NovaDenizen,


You are right, but for this problem it is perfectly OK to use slopes and intersections, and much simpler as you say is middle-school's slope-intersect.

>>and much simpler as you say is middle-school's slope-intersect.

I would have to disagree, I feel that the method Nova and I provided is much cleaner and utilizes the concepts of vector algebra.

post your solution then, teach us all, if you will

sqrt( r² - | A × ||-20,-7|| |²) - A · ||-20,-7||
utilizes the concepts of vector algebra and gets the desired  length of the blue line more directly

>>post your solution then, teach us all, if you will

I posted a solution long ago :)

I've been evaluating ozo's & sirnam's solutions. I want to use the computationally lightest method since this will go into a collision response algorithm for a video game (a  hobbyist venture, I won't quit my day job).  I am intrigued by ozo's latest method because it only needs to find a squarr root once (sqrt being computationally heavier than multiplication or division). Ozo's original method had 2 sqrts, siranm's xls had 5. I'd like to understand Brian's method but I've never heard of linear multiples before and feel like the dumb kid in the back of the class who needs everything explained to the nth degree. (if you wouldn't mind Brian, I'm all ears, I'd really like to understand what is going on with them in this application. I do understand vectors and actually prefer thinking in terms of them).

My original plan was to create a vector along the Z axis and perform a cross product with the red line to get that perpendicular vector that ozo first introduced. Normalize that new perp vector, normalize the vector going to point A, Dot product them to find their projected length relationship, apply that factor to the length of the A vector (the before normalized one) to get the length of the perp. sqrt of 100-perp^2 = distance from perp to edge, that minus the distance from perp to A is length of blue line. *I only know of cross & Dot products from using built in functions of directX, not because I know much about math*

This just seemed like a ton of code that I thought might be lessened by more experienced mathematicians like you guys so I asked this question and am wanting to evaluate the various methods to decide the best one for my case.

In a practical sense when the game runs, point A (an obstacle in the 3d world)  could be anywhere inside the circle and the red line (representing the circle's velocity) could point in any direction & have any magnitude except zero. The circle must be backed out of the obstacle opposite the way it came in until just clear of it and a new "reflected" velocity computed. The blue line represents the distance it must back out and that is why it will always be parallel to the red.

I'm going to try ozo's latest method & Nova's method now.

BTW, my method & siranm's agreed the length of the blue at 4.726. I got 4.86 using ozo's first method. Do you guys think that may be just rounding errors? I thought it seemed a little much for that.

@ ozo,
Does the x & the . in your latest refer to cross & dot? also, I assume the verticals |#| refer to magnitude, is there significance to a double ||#|| or is that just differentiating the magnitudes apart?

@ Nova,
>>which is in line with A, in the direction of C
When you say "in the direction of C" you don't mean "pointing towards the point C", but the C vector's direction, Right?

||-20,-7|| involves sqrt

you should have gotten
4.726263606845579749
for sqrt(10**2-((-7*-4.5) - (-20*6))**2/(((-7)**2 )+ ((-20)**2))) - ((-20*-4.5) + (-7*6))/sqrt(((-7)**2) + ((-20)**2))

I had a small typo, should be:

 (-20m - 4.5)^2 + (-7m + 6)^2 = 100

ozo,

I just learned from wiki that a double ||#|| usually means a normalized vector whereas a single vertical |#| means the magnitude of a vector. Is that the way you meant it? Also, I assume that the magnitude is always positive. correct me if wrong though.

Am I reading the following correctly;;

the sqrt of ( r^2 - the magnitude of vector A crossed with the norm of C (as Nova labled -20,-7)) - the dot product of vector A to that same normalized C.

I was using ||-20,-7|| to be the unit vector in the (-20,-7) direction =  (-20,-7)/|-20,-7| =  (-20,-7)/magnitude(-20,-7)

>>I just learned from wiki that a double ||#|| usually means a normalized vector

I think you're confusing "norm" with "normalized vector," the norm of a vector is simply the length, while a "normalized vector," or "unit vector," is the vector divided by the norm.

Does that help?

If we let C^ = ||-20,-7|| =  C)/magnitude(C) = (C)/sqrt( C dot  C )
A^ = A/(A dot A)
then b= (sqrt( r² - |A cross C^|²)  -   A dot C^)
B = A + b*C^
If the path of A gets reflected by the circle at that point
the reflected position of A will be
A + B*((b*C^) dot B *2/r)
and the new velocity will be ||A + B*((b*C^) dot B *2/r)  - B|| * |C|

More simply, if the velocity was -C before the reflection, the reflected velocity will be
-C + 2*(-C dot B)*B/|B|

I insist... for the very simple question that was initially asked (and already answered), linear algebra is like a cannon to kill a mosquito

Equations of Line and Circle are just fine... and more intuitive in my opinion... at least basic.

I did think norm & normalized were the same. Thanks for pointing that out. So ozo meant |#| = length of original vector. & ||#|| means unit length vector in that direction.

Brian your method now make complete sense. I only stumble on the last part about solving the quadratic equation because that's not something I do often (er.. ever). It's probably a simple thing in your mind. It's the same place I needed siranm to help me through. But being accustomed to working in vectors, I do follow your line of thinking to get to that point.
Believe it or not I have trouble taking (-20m - 4.5)^2 + (-7m + 6)^2 = 100 plugging it into the quadratic equation. Do I plug it into: http://upload.wikimedia.org/math/3/e/a/3ea647783b5121989cd87ca3bb558916.png
and if so what do I use for a, b, c? or do I just somehow get m alone on one side to solve for it & plug that into  r = (-20m - 4.5, -7m + 6)? Thanks for hanging with this Brian.

Brian, is your 'm' and Nova's 'alpha' representing the same concept of a lineal multiple?


ozo,
A bonus, help on the reflection too. Thanks.

More specifically about point A. It is stationary in my game world. well, let me back up. we've been using the circle's center as our world's origin, actually it is only the circle's origin. The circle is a billiards ball on a pool table & the pool table's surface's center is (0, 0, 0). The game is 3d but pool balls (lineally anyways) kind of operate in 2d so I asked this Q in 2d. Now, think of the bumper on the edge of the pool table and where it turns 45 degrees to go into the corner pocket area. That nose of the bumper is represented by point A and the circle is the Ball. The red line is the distance & direction the ball has been traveling between frames. Two reflection planes meet at point A and I will have to sort out how collision proximity to the nose affects the effective reflection plane before I can determine accurate reflection. (most likely I'll end up with the equation you just submitted :-)). So when you say "the reflected position of A" does make sense in terms of ball space but not world space so.... shoot, where was I?  dang. Well, let me get the reposition correct before dealing with the reflection. Heck, that'll be worth another 500 point anyways.

>>Brian, is your 'm' and Nova's 'alpha' representing the same concept of a lineal multiple?

Yep, Nova was saying the same thing using alpha. Alpha is a scalar that is meant to represent a linear multiple of the red vector.

What are all those "vertical lines" he was talking about?

For a vertical line, the slope is "infinite"

m = y2-y1/x2-x1 = infinite, if x2=x1 (vertical line)

for horizontal lines, m=0

the vector (0,1) cannot be defined with a slope, for example.

I see, at times my red vector may be either vertical or horizontal. That tells me that maybe the vector algebra may be the more robust way to code it.

I realize that the original question posed did not account for that requirement so that will not factor into the points award.

I have implemented ozo's latest formula into code and it gives the same result as I got with my way & siranm's way (and probably ozo's original way if I didn't botch the arithmetic).

public float Penetration(Vector3 ballPosition, Vector3 linealMomentum)
{
    float result;
    Vector3 a = new Vector3(-4.5f, 0f, -6f);// transform from ball space to world space
    Vector3 v = new Vector3(-20f, 0f, 7f);//testing only, use linealMomentum.
    v.Normalize();
    float length1 = Vector3.Cross(a, v).Length();
    length1 *= length1;
    float t1 = (float)Math.Sqrt((radius * radius) - length1);
    float t2 = Vector3.Dot(a, v);
    result = t1 - t2;
    return result;
}

3 square roots
20 multiplies
6 additions
8 subtractions
1 divide

Brian,
If you help me work your solution to the end (through the quadratic part), I'll put it into code & add them up too to see if it's lighter.

ozo,

A result vector of a cross product, although creating a vector orthogonal to both vectors, always has a magnitude of the product of the two vectors. direction doesn't concern us here.

So.. since one of the vectors had a magnitude of 1 (the one we normalized to unit length), Why go through the process of crossing it in the first place? it is just going to result in the length of A.

Why not simplify to :

sqrt( r² - | A |²) - A · ||-20,-7||

that would eliminate the cpu resources needed to find the magnitude of the crossed vector.

if.. you don't think it would cause me troubles elsewhere

oops, that only works when the two vectors crossed are orthogonal to each other.

I'll stick with it how you wrote it.

>>A result vector of a cross product, although creating a vector orthogonal to both vectors, always has a magnitude of the product of the two vectors

The problem with the cross product is that it's a VECTOR product, meaning the result is also a vector.

The cross product produces a vector whose magnitude is |a| * |b| sin(angle between) and direction orthogonal to both. You should NOT use the cross product to obtain a product of magnitudes.

You should be using the scalar (dot) product for this.

square of the dot product with the vector perpendicular to (-20,-7) was the original concept,
but lacking a simple vector notation for that operation, I expressed it as magnitude of the cross product with ||-20,-7|| when I phrased it in terms of vector operations.

Thank you all. I awarded most point to ozo because he realized I needed the solution in a form that only arithmetic was needed to solve and presented that first. After that siranm assisted me to get the solution using slope & a quadratic equation. And lastly to brian because I know there is value to his approach but I wasn't able to follow through with it.

Again, thank you all, I learned much from this thread.