comparing two angles

Given four points in the plane, A,B,X,Y, I wish to determine which of the following two angles is smaller ∢ABX or ∢ABY.

The angle ∢ABX is defined as the angle of BX, when AB is translated to lie on the open segment (-∞,0]. Intuitively when saying ∢ABX I mean the angle you get when you turn left after visiting vertex B.

I'd rather not use cos or sqrt, in order to preserve accuracy, and to minimize performance (the code would run on an embedded system).

In the case where A=(-1,0),B=(0,0), I can compare the two angles 开发者_StackOverflow社区∢ABX and ∢ABY, by calculating the dot product of the vectors X,Y, and watch its sign.

What I can do in this case is:

1. Determine whether or not ABX turns right or left
2. If ABX turns left check whether or not Y and A are on the same side of the line on segment BX. If they are - ∢ABX is a smaller than ABY.
3. If ABX turns right, then Y and A on the same side of BX means that ∢ABX is larger than ∢ABY.

But this seems too complicated to me.

Any simpler approach?

Here's some pseudocode. Doesn't detect the case when both angles are the same. Also doesn't deal with angle orientation, e.g. assumes all angles are <= 180 degrees.

v0 = A-B
v1 = X-B
v2 = Y-B

dot1 = dot(v0, v1)
dot2 = dot(v0, v2)

if(dot1 > 0)
  if(dot2 < 0)
    // ABX is smaller
  if(dot1 * dot1 / dot(v1,v1) > dot2 * dot2 / dot(v2, v2) )
    // ABX is smaller
  // ABY is smaller

if(dot2 > 0)
  // ABY is smaller
if(dot1 * dot1 / dot(v1,v1) > dot2 * dot2 / dot(v2,v2) )
  // ABY is smaller
// ABX is smaller

Note that much of this agonizing pain goes away if you allow taking two square roots.

Center the origin on B by doing

X = X - B
Y = Y - B
A = A - B

EDIT: you also need to normalise the 3 vectors

A = A / |A|
X = X / |X|
Y = Y / |Y|

Find the two angles by doing

acos(A dot X)
acos(A dot Y)

===

I don't understand the point of the loss of precision. You are just comparing, not modifying in any way the coordinates of the points...

You might want to check out Rational Trigonometry. The ideas of distance and angle are replaced by quadrance and spread, which don't involve sqrt and cos. See the bottom of that webpage to see how spread between two lines is calculated. The subject has its own website and even a youtube channel.

I'd rather not use cos or sqrt, in order to preserve accuracy.

This makes no sense whatsoever.

But this seems too complicated to me.

This seems utterly wrong headed to me.

Take the difference between two vectors and look at the signs of the components.

The thing you'll have to be careful about is what "smaller" means. That idea isn't very precise as stated. For example, if one point A is in quadrant 4 (x-component > 0 and y-component < 0) and the other point B is in quadrant 1 (x-component > 0 and y-component > 0), what does "smaller" mean? The angle of the vector from the origin to A is between zero and π/2; the angle of the vector from the origin to B is between 3π/4 and 2π. Which one is "smaller"?

I am not sure if you can get away without using sqrt. Simple:

AB = A-B/|A-B|
XB = X-B/|X-B|
YB = Y-B/|Y-B|

if(dot(XB,AB) > dot (YB,AB)){
 //<ABY is grater
}
else
{
...
}

Use the law of cosines: a**2 + b**2 - 2*a*b*cos(phi) = c**2

where a = |ax|, b =|bx| (|by|), c=|ab| (|ay|) and phi is your angle ABX (ABY)