Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (780) Games in Android Showcase (233) games submitted by our members Games in WIP (857) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 How can I find the angle between two lines?  (Read 10199 times) 0 Members and 1 Guest are viewing this topic.
jessewclark

Senior Newbie

Heaven means muzak.

 « Posted 2004-01-30 01:02:00 »

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
 « Reply #1 - Posted 2004-01-30 03:56:54 »

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

Senior Newbie

Heaven means muzak.

 « Reply #2 - Posted 2004-01-31 00:32:26 »

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

Quote
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.

Quote
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.

Quote
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
 « Reply #3 - Posted 2004-01-31 06:02:43 »

Quote
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.

Quote
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"

Quote
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.

Quote
"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).

Quote
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.
Quote
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.

Quote
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

Senior Newbie

Heaven means muzak.

 « Reply #4 - Posted 2004-01-31 15:06:07 »

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:

Quote
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

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

 « Reply #5 - Posted 2004-01-31 16:50:15 »

Quote
"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).

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
jessewclark

Senior Newbie

Heaven means muzak.

 « Reply #6 - Posted 2004-01-31 23:11:50 »

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
 « Reply #7 - Posted 2004-02-01 05:52:23 »

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

jessewclark

Senior Newbie

Heaven means muzak.

 « Reply #8 - Posted 2004-02-01 21:50:13 »

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

Senior Newbie

Heaven means muzak.

 « Reply #9 - Posted 2004-02-02 19:12:23 »

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

JGO Kernel

Medals: 57
Projects: 11

Monkey for a head

 « Reply #10 - Posted 2004-02-02 19:27:17 »

Quote

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

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

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
jessewclark

Senior Newbie

Heaven means muzak.

 « Reply #11 - Posted 2004-02-02 19:29:58 »

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

Senior Devvie

Medals: 1

Who, me?

 « Reply #12 - Posted 2004-02-02 22:50:37 »

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

Hellomynameis Charlie Dobbie.
jessewclark

Senior Newbie

Heaven means muzak.

 « Reply #13 - Posted 2004-02-03 20:54:55 »

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!
Pages: [1]
 ignore  |  Print

 hadezbladez (1143 views) 2018-11-16 13:46:03 hadezbladez (514 views) 2018-11-16 13:41:33 hadezbladez (1176 views) 2018-11-16 13:35:35 hadezbladez (261 views) 2018-11-16 13:32:03 EgonOlsen (2555 views) 2018-06-10 19:43:48 EgonOlsen (2773 views) 2018-06-10 19:43:44 EgonOlsen (1556 views) 2018-06-10 19:43:20 DesertCoockie (2259 views) 2018-05-13 18:23:11 nelsongames (2109 views) 2018-04-24 18:15:36 nelsongames (2803 views) 2018-04-24 18:14:32
 Deployment and Packagingby philfrei2019-02-17 20:25:53Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org