How to determine if a vector is between two other

问题:

I am looking for a fast and effective way to determine if vector B is Between the small angle of vector A and vector C. Normally I would use the perpendicular dot product to determine which sides of each line B lies on but in this case is not so simple because of the following:

• None of the vectors can be assumed to be normalized and normalizing them is an extra step I would prefer to avoid.
• I have no clear notion as to which side is the smallest angle so it is hard to say which side of the line is good or not.
• It is possible for A and B to be co-linear or exactly 180 degrees apart in which case I want to return false.
• While I am working in a 3D enviroment it is easy for me to simplify this to 2D if that makes things easier and more importantly faster. This test will be used in an algorithm that needs to run as fast as possible.

If there is some easy and efficient method to determine which direction my perpendicular vectors should both point I could use the two dot products for my test.

Another approach I have been considering without much success so far is using a matrix. In theory from what I understand of matrix transforms I should be able to use A and C as basis vectors. Then multiplying B by the matrix I should be able to test what quadrant B then lies in by whether X and Y are both positive. If I could get this approach to work it would likely be the best since one matrix multiplication should be faster than two dot products and I should not have to worry about which side has the smallest angle on it.

The problem is from my tests I cannot simply use A and C as bases and multiply it normally and get correct behavior. I am really not sure what i am doing wrong here. I have run across the term "Vector spaces" a few times which as near as I can figure seems to be a very similar concept to matrix transforms without any requirements for orthogonal bases or orthonormal bases. Is it the same thing as matrix? If not, might there be a better approach and how would I use that?

Just to give a more visual explanation of what I am talking about:

@Aki Suihkonen I can't seem to get it working. Coded up a mock case I could run through and see if I can't figure somthing out

For this case using

Ax 2.9579773 Ay 3.315979

Cx 2.5879822 Cy 5.1630249

For B I rotated around the four quadrants the vectors divide the space up into.

The signs I got: - For Q1 -- - For Q2 +- - For Q3 +- - For Q4 --

Assuming I rotated around in the enviroment the same direction as the image I am fairly sure I did.

回答1:

I think Aki's solution is close, but there are cases where it doesn't work:

From his solution:

return (ay * bx - ax * by) * (ay * cx - ax * cy) < 0;

This is equivalent to checking whether the cross product between B and A has the same sign as the cross product between C and A.

The sign of the cross product (U x V) tells you whether V lies on one side of U or the other (out of the board, into the board). In most coordinate systems, if U needs to rotate counter-clockwise (out of the board), then the sign will be positive.

So Aki's solution checks to see if B needs to rotate in one direction to get to A, while C needs to rotate in the other direction. If this is the case, B is not within A and C. This solution doesn't work when you don't know the 'order' of A and C, as follows:

To know for certain whether B is within A and C you need to check both ways. That is, the rotation direction from A to B should be the same as from A to C, and the rotation direction from C to B should be the same as from C to A.

This reduces to:

if (AxB * AxC >= 0 && CxB * CxA >= 0)

// then B is definitely inside A and C

回答2:

One method to think about this is to regard all these vectors A, B, C as complex numbers.

Multiplying A, C all with B*, which is the complex conjugate of B, both the resulting vectors will be rotated in complex plane so that the reference axis (B*Conj(B)) is now the real axis (or y = 0) -- and that axis doesn't need to be calculated. In this case one only has to check if the sign of 'y' or imaginary component differ. Also in this case both resulting vectors have been scaled by the same length |B|.

`return sign(Imag(A * Conj(B))) != sign(Imag(C * Conj(B)));`

A = ax + i * ay; B = bx + i * by; C = cx + i * cy;
Conj(B) = bx - i * by; 
A * B = (ax * bx - ay * by) + i * (ax * by + ay * bx);

I think this equation leads to even better performance, as only the Imaginary component of the multiplication is needed.

As a full solution, this converts to:

return (ay * bx - ax * by) * (ay * cx - ax * cy) < 0;

The middle multiplication is a short cut for:

return Sign(ay * bx - ax * by) != Sign(ay * cx - ax * cy);

Without complex numbers, the problem can be also seen as vector B being { Rcos beta, Rsin beta }, which can be represented as a rotation matrix.

R*[  cb -sb ]    [ bx -by ],   cb = cos(beta), sb = sin(beta)
  [  sb  cb ] =  [ by  bx ]    cos(-beta) = cos(beta), sin(-beta) = -sin(beta)

Multiplying [ax,ay], [cx,cy] with the transpose of the scaled matrix [bx by, -by bx] affects the lengths of [ax, ay] * rotMatrix(-beta), [cx, cy] * rotMatrix(-beta) in exactly the same way.

回答3:

In polar coordinates, you would just be asking if θ_A < θ_B < θ_C. So transform to polar first:

a_theta = ax ? atan(ay / ax) : sign(ay) * pi