Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (533)
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 4044 times)
0 Members and 1 Guest are viewing this topic.
Offline jessewclark

Senior Newbie




Heaven means muzak.


« Posted 2004-01-30 02: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?
Offline tom
« Reply #1 - Posted 2004-01-30 04: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)

Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #2 - Posted 2004-01-31 01: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!
Legends of Yore - The Casual Retro Roguelike
Offline tom
« Reply #3 - Posted 2004-01-31 07: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  Smiley 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"  Wink

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

Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #4 - Posted 2004-01-31 16: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.
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #5 - Posted 2004-01-31 17: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 ]
Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #6 - Posted 2004-02-01 00: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?
Offline tom
« Reply #7 - Posted 2004-02-01 06:52:23 »

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

Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #8 - Posted 2004-02-01 22: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!
Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #9 - Posted 2004-02-02 20: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!
Legends of Yore - The Casual Retro Roguelike
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


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

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

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

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

Senior Newbie




Heaven means muzak.


« Reply #11 - Posted 2004-02-02 20: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.
Offline cfmdobbie

Senior Member


Medals: 1


Who, me?


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

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

Hellomynameis Charlie Dobbie.
Offline jessewclark

Senior Newbie




Heaven means muzak.


« Reply #13 - Posted 2004-02-03 21: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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (26 views)
2014-07-24 01:59:36

Riven (25 views)
2014-07-23 21:16:32

Riven (20 views)
2014-07-23 21:07:15

Riven (22 views)
2014-07-23 20:56:16

ctomni231 (51 views)
2014-07-18 06:55:21

Zero Volt (46 views)
2014-07-17 23:47:54

danieldean (37 views)
2014-07-17 23:41:23

MustardPeter (40 views)
2014-07-16 23:30:00

Cero (56 views)
2014-07-16 00:42:17

Riven (55 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!