How can I find the angle between two lines?

[jessewclark]

I've looked through the .geom package, and I can't find anything that does this.  Here's my goal: I have two line segments that intersect, and I want to find the angle between them.

I've thought of one way to do it.  It's pretty convoluted.  First, find the intersection of the two lines by choosing one line and using a PathIterator to count through the points on that line until we find the point with a distance of zero from the other line.  There's our intersection.

Next, create two lines of equal size, thus: find the shorter of the two lines; create a new line (if necessary) that is identical to the longer line, but whose P1 is at the intersection of the two lines; use a PathIterator again to count through the points on the longer line until we've defined a segment of the longer line that is the same length as the shorter line.  

Now we should have two lines of equal length.  This length is the radius of the circle we need to create to find the angle between the lines.  But what we need to actually define is the rectangle that *bounds* the circle that encompasses the lines.  We can do that by starting from the intersection point and subtracting the segment length from the x and y of that point.  That should give us the location of the upper left corner of the rectangle we're looking for.

Now, the last leg of this process: iterating through a bunch of different Arc2Ds. Using the endpoint of one of the lines as a startPoint for the arcs, we iterate to find an arc whose endPoint is 0 distance from the second line.  Once we've found the startPoint and the endPoint of an arc that runs from one line to the other, the parameter that defines the degrees of that arc segment will also give us the angle between the two lines.  Voila!

Whew.

That's the simplest (hah!) method I can think of.  I'd love to hear of another.  Anyone?

[tom]

The formula is a dot b = |a||b|cos a. So take the acos of the the dotpruduct between the normalized vectors. Here is an explanation:

Lets say you have the two lines given by the their endpoints (A1, A2) and (B1, B2).
Firt get the lines vectors between the endpoints (subtract x,y,z):
A = A2-A1
B = B2-B1

Normalize the vectors:
ALength = Math.sqrt(A.x*A.x+A.y*A.y+A.z*A.z)
A.x /= ALength
A.y /= ALength
A.z /= ALength
// same with vB

Then take the dot product between the vectors:
dot = (A.x*B.x) + (A.y*B.y) + (A.z*B.z);

Now dot is the cos of angle and the angle is:
angle = Math.acos(dot)

[jessewclark]

Wow, that is way over my head.  I barely understand any of it.

a dot b = |a||b|cos a

Uh, what do a and b represent here?  Vectors, you say?  Does that mean the same thing as "line segments?"  And (feeling stupid, he asks:) what does "dot" mean?  And what does "|a|" mean?  From context, I assume it represents a "normalized" vector, but I don't know what that is.  You show me the calculations for normalization later on in your post, but I have no idea what you're doing or why.

Firt get the lines vectors between the endpoints (subtract x,y,z):
A = A2-A1
B = B2-B1

"Subtract x,y,z?"  Hah?  It looks to me like A and B are points, here, since they're derived by subtracting one point from another, but I'm not sure how you do that.  Subtract A1.x from A2.x and A1.y from A2.y?  What is this "z" I keep hearing about?  And if A and B are points, why are they "Vectors?" Confused = me.

A.x /= ALength
A.y /= ALength
A.z /= ALength

What does "/=" do? <------ another embarassing question.


Finally, exactly what angle does this calculation produce?  If the lines intersect without having a common endpoint, there are actually two angles formed by the lines (if I remember correctly, an "acute" angle and an "obtuse" angle, but I wouldn't bet on it).  Which angle would this calculation return?  Or would it only work if the line segments have a common endpoint (which actually would work fine for me)?

Thanks for your post, sorry I'm so dumb.

Games published by our own members! Check 'em out!

[tom]

Uh, what do a and b represent here?  Vectors, you say?  Does that mean the same thing as "line segments?"

A Vector is a line segment where the first endpoint is in the origin (0, 0). This means that a Vector only represent the direction and length of a line. So a and b represents the direction and length of the two line segments.

what does "dot" mean?

dot stands for dot product, also called scalar product. Is one of two ways you can multiply vectors. Is defined as "the product of two vectors to form a scalar, whose value is the product of the magnitudes of the vectors and the cosine of the angle between them"

And what does "|a|" mean?  From context, I assume it represents a "normalized" vector, but I don't know what that is.  You show me the calculations for normalization later on in your post, but I have no idea what you're doing or why.

|a| means the length of vector a. Let's look at the formula:
a dot b = |a||b|cos angle

we wan't to solve this to get angle:
cos(angle) = (a dot b) / (|a| |b|)

Normalizing a vector means making the length of the vector equal 1. This makes |a| |b| become 1*1. So if a and b is normalized the formula becomes:
cos(angle) = (a dot b)/(1 * 1)
cos(angle) = (a dot b)

finally to solve the equation:
angle = Math.acos(a dot b).

(a dot b) returns a single value not a vector.

The Vectors are normalized by dividing x and y with the length of the Vector.

"Subtract x,y,z?"  Hah?  It looks to me like A and B are points, here, since they're derived by subtracting one point from another, but I'm not sure how you do that.  Subtract A1.x from A2.x and A1.y from A2.y?

Yes, subtracting the points. So
C = B - A
means
C.x = B.x - A.x
C.y = B.y - A.y
Wich makes C a Vector. Because we have moved the line segment (A, B) so that it A starts in origo (0, 0).

What is this "z" I keep hearing about?

That is the third dimension   I was not sure if you used 2d or 3d lines. The algorithm is identical.

What does "/=" do?

This is java code. "A.x /= ALength" is the same as A.x = A.x / ALength". It's just a little less code.

Finally, exactly what angle does this calculation produce?

Given the lines A and B represented by the enpoints (A1, A2) and (B1, B2). This calculation gives you the angle between the lines in the range 0 throug pi. The order of the endpoints matter because it defines the direction of the Vectors. The lines do not have to intersect. You can think of it as the lines are moved to the intersection point of the rays (infinite lines not segments), where the calculations is done.

It gives you the absolute angle of the two vectors A and B. Absolute angle means there are two solutions. The second solution is (2*PI-angle). To find out wich to use you can use the "cross-product"  

If you want understand it better you can read up (google) on vector math. I found this when I searched for "angle between lines": http://www.netcomuk.co.uk/~jenolive/vect14.html

[jessewclark]

Tom, thanks for your efforts.  I still just barely understand.  I looked at the website you referred me to, but it too was too hard for me to understand.  I'm not sure you should put any more work into explaining it to me.  There is one thing I'd like you to explain a little more about:

It gives you the absolute angle of the two vectors A and B. Absolute angle means there are two solutions. The second solution is (2*PI-angle). To find out wich to use you can use the "cross-product"

Again, pretty much lost on me.  Looking at that web page, it doesn't say anything about absolute angle, it just shows one solution.  Does absolute angle mean it's always the smaller of the two possible angles?

"2*Pi-angle" confuses me.  If there are two solutions, isn't solution b=180 minus solution a?  Is that not true because the answer will be in radians and not degrees?  If so, don't I need to do some kind of multiplication to solution a, also?

Actually, I'm not sure whether you should bother explaining any of that.  I'm willing to take your word for it and just try using the calculations you provide.  I just need to know how to find the smallest of the two possible angles, in degrees.

[Orangy Tang]

"2*Pi-angle" confuses me.  If there are two solutions, isn't solution b=180 minus solution a?  Is that not true because the answer will be in radians and not degrees?  If so, don't I need to do some kind of multiplication to solution a, also?

Using the dot product as above will always get you the smallest angle between two angles, but obviously theres a bigger angle that exists:

1   2   3   4   5   6

|   / |a/ | / |/ b

The smallest angle is clearly 'a', yet the largest angle 'b' loops all the way around the other way. So b = 360 - a (or b = 2PI - a in radians).

[jessewclark]

OT:

I get you, but I was thinking of this situation:

1   2   3   4   5   6   7   8   9

|     /       |    /       |a /       | /       |/      /|b     / |    /  |   /   |

in which b = 180 - a.

So that leaves only my other question: will the dot calculation produce an angle in degrees or in radians?

[tom]

In radians, becuase Math.acos returns the result in radians. But you can convert it to degrees by using Math.toDegrees().

[jessewclark]

Thanks, Tom and OT.  Thanks for explaining so much to me.  Now all I have to do is use this stuff in my code.  Wish me luck!

[jessewclark]

Oops.  I posted some code, 'cuz it wasn't working, and I was asking if anyone could see an error in it, and while I was posting it I saw the error in it.

Nevermind!

Games published by our own members! Check 'em out!

[Orangy Tang]

   

1	double dot = ( newAX * newBX ) + ( newAY + newBY ) ;

Typo? Dot product is aX*bX + aY*bY
Looks good other than that.

[jessewclark]

OT:  I don't see the difference between what you wrote and what I coded.

The error I spotted was that while I was normalizing the vectors I was dividing B.x and B.y by Alength instead of Blength.

[cfmdobbie]

Second term should be multiplied together, not added.  Small typo.

[jessewclark]

Oops.  I looked and looked and looked at that, and didn't see it.  Embarassed, once again, me.

On the plus side, I've got the code in and now it's working perfectly! Yayy!  Thanks to all!