How to determine whether V3 is between V1 and V2 when we go from V1 to V2 counterclockwise?

Question

I have three vectors V1, V2, and V3. Their origin points are on the axes' origin. How could I determine whether V3 is between V1 and V2 when I move around counterclockwise from V1 to V2?

alt text http://www.freeimagehosting.net/uploads/1448ea8896.jpg

It can't be done with obtaining their angles and evaluating these kind of conditions (pseudo-code):

if angle(V3) > angle(V1) && angle(V3) < angle(V2) 
   printf("V3 is between V1 and V2") 
else 
   printf("out of the interval")

To see its defect, suppose that the angle function gives angles in the range of [-pi pi]. So, if angle(V1) = 120 (in degree), angle(V2) = -130 and angle(V3) = 150 then the answer (according to the above code) is "out of the interval" although if you move around counterclockwise from V1 to V2, it is between them.

You may suggest adding 2*pi to angle(V2) or something like that, but I've tried such things and it doesn't work.

I'm programming in MATLAB.

EDIT 1 : it is in 2D.

Answer 1

Since you are doing this in MATLAB, here is one solution that should work:

crossProds = [V1(1)*V2(2)-V1(2)*V2(1) ...
              V1(1)*V3(2)-V1(2)*V3(1) ...
              V3(1)*V2(2)-V3(2)*V2(1)];
if (all(crossProds >= 0) || ...
    (crossProds(1) < 0) && ~all(crossProds(2:3) < 0)),
  disp("V3 is between V1 and V2");
else
  disp("out of the interval");
end

EXPLANATION:

The cross product between the 2-D vectors V1 and V2 is stored in the first element of crossProds. This value will be greater than or equal to zero if the counter-clockwise angle between V1 and V2 is between 0 and 180 degrees, inclusive. In this case, when V3 is between V1 and V2 in the counter-clockwise direction then the cross products (V1,V3) and (V3,V2) are also greater than or equal to zero. This explains the first logical check:

all(crossProds >= 0)

If the counter-clockwise angle between V1 and V2 is greater than 180 degrees, then the cross product of these two vectors will be less than zero. In this case, when V3 is between V1 and V2 in the clockwise direction then the cross products (V1,V3) and (V3,V2) are also less than zero. Therefore, if these cross products are not both less than zero then V3 must be between V1 and V2 in the counter-clockwise direction. This explains the next two logical checks:

(crossProds(1) < 0) && ~all(crossProds(2:3) < 0)

The above logical checks should cover all possible situations. The operators || and && are short circuit operators in MATLAB: they will skip the second statements if they are not necessary. For example, if the first statement in an OR is true, there is no reason to check the second statement since only one argument in an OR needs to be true for the result to be true.

Answer 2

Calculate angle(V1), angle(V2) and angle(v3) (a1, a2, a3).

Modify a2 and a3 (add 2*pi if needed) so that

a1 <= a2 < a1 + 2*pi
a1 <= a3 < a1 + 2*pi

Now you simply have to compare a2 and a3. V3 is between V1 and V2 is resulting a3 is inferior to a2.

Answer 3

V1 is a red herring. You're just going to confuse yourself thinking about 3 angles at once.

2. Rotate everything clockwise by angle(V1)
3. Normalize the remaining two angles to [0,360)

Now the question is simply to compare norm(angle(V2)-angle(V1)) and norm(angle(V3)-angle(V1)).

Answer 4

Somewhat easier method for most other programing languages.

If V1, V2 and V3 are given vectors, and we need to decide weather V3 is between V1 and V2, and Ri = atan2(Vi) (which returns an angle in radians from -pi to pi):

Clockwise:

R1 -= R3;
R2 -= R3;

if (R1 < 0) R1 += 2 * PI;
if (R2 <= 0) R2 += 2 * PI;

return (r1 < r2);

For counterclockwise, just swap R1 and R2.

Answer 5

To test this condition you have to calculate the winding of two triangles:

1. The triangle formed by V1, the origin and V3. This triangle must be counter-clockwise.

2. The triangle formed by V3, the origin and V2. This triangle must be counter-clockwise as well.

To test the winding of a triangle it's enough to check the sign of the 2D cross-product of the vertices.

The test looks like this (sorry - C-code):

int IsBetween (vector v1, vector v2, vector v3)
{
  float winding1 = (v1.x * v3.y - v1.y * v3.x);
  float winding2 = (v3.x * v2.y - v3.y * v2.x);

  // this test could be exactly the wrong way around. This depends
  // on how you define your coordinate system (e.g. is Y going up or down?)

  if ((winding1 <0) && (winding2 < 0))
  {
    printf ("V3 is between them\n");
  }
  else
  {
    printf ("it's not\n");
  }
}