finding angle between 3 points

xbeanx · Post by **xbeanx** » Tue Oct 28, 2003 10:30 pm

I want to find the angle (in degrees) of three points.

I am trying to use the java Math.atan2(p1, p2) method, but am not getting what I want.

Take for example the points

(2, 2)(1, 1)(3, 1) the angle can be found by doing this:

angle1 = atan2( (1-1), (1-3) )
angle2 = atan2( (2-1), (2-1) )

angle = angle2 - angle1

This gives (after conversion to degrees) 45.0 which is correct.

But, if I change the points to (2, 2)(3, 3)(1, 3) I get back -315. I should be getting 45.0 again. This is because of the way polar coordinates work. For example, an angle of 181 degrees would actually be -179.

I dunno if any of this makes sense, but could someone help me figure out a good way to find the angle between these three points???

Farid Ahmadov · Post by **Farid Ahmadov** » Tue Oct 28, 2003 11:39 pm

k1=(2-1)/(2-1)
k2=(1-1)/(1-3)
k1=tg(alfa) where alfa angle 0<alfa<=2*pi
k2=tg(betta) "----------------------------------"
let gamma be angle between this three points then
tg(gamma)=tg(betta-alfa)=(tg(betta)-tg(alfa))/(1+tg(alfa)*tg(betta))=(k2-k1)/(1+k1*k2)
gamma = arctan((k2-k1)/(1+k1*k2))

It is a common way to find angles between two lines. I hope it will help.

Joseph Kurniawan · Post by **Joseph Kurniawan** » Wed Oct 29, 2003 7:12 am

Can you specify more which angle you want to find??
Check this out:

*A

*B *C

From these three points, there are three angles can be formed:
1. ABC
2. ACB
3. BAC

So which angle do you want to calculate?

junjieliang · Post by **junjieliang** » Wed Oct 29, 2003 11:51 am

Well I'm not too sure, but would using cosine rule cause a loss in precision? Using pythagoras's theorem for the lengths, then cosine rule for the angle: angle = acos[(a^2+b^2-c^2)/(2ab)]. The loss in precision could then come in through the acos(), and the sqrt() needed for the 2ab. For a^2, b^2, c^2 no sqrt is needed.

xbeanx · Post by **xbeanx** » Wed Oct 29, 2003 12:48 pm

Farid, I found your post a little hard to understand. What is tg() ??

Joseph, the angle I want to find... It may change. Can you tell me a way to find an angle and I'll adapt my program to it?

xbeanx · Post by **xbeanx** » Wed Oct 29, 2003 3:17 pm

Sorry about the last post, I was rushing so I didn't get to give a good reply.

Basically, I want a function that can take three points, A,B,C and return the angle formed by ABC. So I am looking for angle B.

My current way is this:
[java]
public static double getAngle(Point p1, Point p2) {
return Math.toDegrees(Math.atan2(p2.y-p1.y, p2.x-p1.x));
}

[...]

double baseAngle = getAngle(point2, point3);
double angle = getAngle(point1, point2) - baseAngle;
[/java]

For the following points it returns the following angles:

Code: Select all

(2,2)(1,1)(3,1) :: 45.0
(2,2)(3,1)(3,3) :: 45.0
(2,2)(3,3)(1,3) :: -315.0
(2,2)(1,3)(1,1) :: 45.0

The angle should be 45.0 for all of them. But for the third one it gives me a -315. Can anyone help me fix my broken code??

Does anyone know of a good way to get these angles? I've searched the net but can't find anything that helps. Thanks!!

Joseph Kurniawan · Post by **Joseph Kurniawan** » Wed Oct 29, 2003 4:26 pm

Well xbeanx, if your problem is only to rid of the negative angle (I assume that your algo to calculate angle is correct), you just need to add conditional statement:

Code: Select all

if ( angle > 360 || angle < -360 ) angle = floor ( angle / 360 )
if ( angle < 0 ) angle = 360 + angle

I think those two conditional statement should be enough to fix your problem.

xbeanx · Post by **xbeanx** » Wed Oct 29, 2003 4:39 pm

Joseph, thanks for trying to help.

Unfortunately, my problem is not just with negative angles... It is more with consistency.

If I get the angle (2,2)(1,1)(3,1) it should be 45.0
If I get the angle (2,2)(3,1)(1,1) it should be -45.0
(one turns right, the other left)

The 4 angles I gave as examples earlier:
(2,2)(1,1)(3,1) :: 45.0
(2,2)(3,1)(3,3) :: 45.0
(2,2)(3,3)(1,3) :: -315.0
(2,2)(1,3)(1,1) :: 45.0

Should all be 45.0. I know why the -315 is in there, but I don't know how to effectively get rid of it without affecting the other 3 angles.

wsarzynski · Post by **wsarzynski** » Wed Oct 29, 2003 5:12 pm

do you really need this angle ?
i did quite a lot of geometry and inconsistency was never a problem.
Check a hint for problem 109, bottom of problem description,
- detection of orientation.

wsarzynski · Post by **wsarzynski** » Wed Oct 29, 2003 6:25 pm

i think you should subtract p2 from both p1 and p3.
this should work when p1 p2 p3 counter-clockwise oriented.

Code: Select all

x1 -= x2; 
y1 -= y2;
x3 -= x2;
y3 -= y2;

double angle1 = atan2(y1, x1);
double angle2 = atan2(y3, x3);

if( angle1 < 0.0 ) angle1 += 2*M_PI;
if( angle2 < 0.0 ) angle2 += 2*M_PI;

return 180.0*(angle1 - angle2)/M_PI;

xbeanx · Post by **xbeanx** » Wed Oct 29, 2003 6:55 pm

I fixed it with
if(Math.abs(end1Angle) > 180) end1Angle += (end1Angle < 0) ? 360 : -360;
if(Math.abs(end2Angle) > 180) end2Angle += (end2Angle < 0) ? 360 : -360;

It took me a while to figure it out, but it works fine now.

As for the reference to P109... I solved that one no problem with the same code I was using here. I guess it didn't make much of a difference in that problem.

wsarzynski · Post by **wsarzynski** » Wed Oct 29, 2003 7:56 pm

Hint in 109 says you don't need to compute angles to sort by angles,
it is an optimization issue. I try to avoid angles.

xbeanx · Post by **xbeanx** » Wed Oct 29, 2003 9:08 pm

This was actually a problem with 132 for me.

What I was trying to do is draw a line from the centre of mass to each end, then check that the angles of these lines are <= 90 degrees. That way I can check if the point lies between the endpoints.

Anyway, it worked and I got accepted. Does anyone know an easy way to check if the centre of mass is between the endpoints for this problem?

Farid Ahmadov · Post by **Farid Ahmadov** » Wed Oct 29, 2003 10:49 pm

tg() is tangent in math or sin()/cos() in pascal or k for line. What I wrote is just formula to find angle between two lines, the common situation of three points.
2xbeanx
To solve this problem just make convex and check if mass center is above
sides of this convex. But if you have problems with angle you can check if all points are on one side of a line. You don't even make convex for it. You know formula y=k*x+b. First get k1 and b1 for two points. Then I b of other points with initial k1. If all this points are greater or less than b1, then all is OK.
Algo:

Code: Select all

for i:=1 to n do
for j:=i+1 to n do
begin
  check(i,j,t);
  if t<>-1 then
  begin
    if t<min then min:=t;
  end;
end;

The main part is of course check. Convex method is faster than this method. But if you have problems with angles this is a best method (I think so).