Archived

This topic is now archived and is closed to further replies.

Angle between two points.

This topic is 5144 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''ve run in to a bit of a trig problem. My program is running under a very limited environment: no floating point, no trig functions, no sqrt. That said, I''ve created fixed point sin, cos, and tan tables. I''ve implemented a fixed point multiply, but have avoided division. Assume that my division has 0 decimal places of accuracy. My problem is: Give two points on a plane, A(x,y), B(x,y), how can I determine the angle between them? Is this even possible with what I have? If not, what function(s) would I need to solve this problem? Thanks, Will

Share this post


Link to post
Share on other sites
Assuming you mean the angle between the lines from the origin to the two points (you really should be clearer/specific as Blue Phoenix said...), you could use the dot product

(Ax, Ay).(Bx, By) = |A||B|cos(angle)

where (Ax, Ay) is the vector A, (Bx, By) is the vector B, |A| and |B| are the magnitudes of the vectors A and B respectively and angle is the angle (in radians) between the vectors.

Ax*Bx + Ay*By = sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By)*cos(angle)

cos(angle) = (Ax*Bx + Ay*By)/(sqrt(Ax*Ax + Ay*Ay)*sqrt(Bx*Bx + By*By))

So you''d need to have an inverse cosine function to find the angle, I believe...

Share this post


Link to post
Share on other sites
Geoff, did you even read RP's post? he's using fixed-point...

Will, if you're okay with receiving an approximation of the angle you can use the following instead of acos.

angle = fixedpoint(90) - dotproduct(a,b)/(length(a) * length(b))) * fixedpoint(90);

where dotproduct(a,b) is a.x*b.x + a.y*b.y

The problem comes in with the length(a) and length(b) as well as the division required there with the fixed-point. But at least you can eliminate acos.

by the way, what is the bit-depth of your fixed point operations?
16.16, 8.8, 32.32, 24.8, 8.16? Division in fixed-point is a bit more tricky, you may have to use intermediate variables to store the high-part for you. Also, there are some good fixed-point square root functions out there - classic example is one of John Carmack's Quake1/2/3 (not sure which version)...

if you understand ASM, here's an interesting tutorial...
http://www.geocities.com/SiliconValley/Lakes/4543/fix1.txt

BTW, what hardware are you developing for?

[edit]
another link:

http://www.mactech.com/articles/mactech/Vol.10/10.03/FixedPointMath/

has some c++ 16.16 fixed point sqrt code.
[/edit]

[edited by - FReY on November 11, 2003 8:45:42 AM]

Share this post


Link to post
Share on other sites
Thanks to everyone who has replied.

Blue Phoenix and kin: Yes, I should have said the angle between two vectors.

Thanks very much for the links, I'll check them out.

I'm using 18.14 fixed point. My environment is Java 2 Micro Edition.

The only thing that worries me about the proposed soltions is the division.

When I get home I'll try implementing the proposed solutions. I'll check if I the 64 bit Long is actually implemented supported.. This would make life a bit easier.

Thanks,
Will


[edited by - RPGeezus on November 11, 2003 1:44:36 PM]

Share this post


Link to post
Share on other sites
Its also easy to make a division lookup table.

1/n, then multiply. Best ofcourse to set the fixed point at the most significant bit here.

There are some very fast (but less accurate) methods to calc the sqrt with superspeed. Back in the assembly days, these were often used for phong shading.
Like FReY said , carmacks sqrt use might be good. But if i remember correctly, he used them for texture perspective.

The phong shading could be a better example to lookup. Because this is more focussed on a 1/sqrt for normalization (like you need).

Share this post


Link to post
Share on other sites