Sign in to follow this  

Robust test if two vectors are collinear and testing affine dependence

This topic is 3568 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 wonder what is the most robust way to test whether two vectors are collinear. A simple idea would be to use the cross product: A = | a x b | < epsilon This becomes unstable if a and b differ greatly in length. I could normalize a and b before since this is a direction test, but I wonder if there are better solutions to this problem? The same question can be extented when I want to test if two, three or four points are affine dependent. Here I basically test: | a - b | < epsilon | ( b - a ) x ( c - a ) | < 2 * epsilon | ( b - a ) * ( c - a ) x ( d - a ) | < 6 * epsilon Especially both tests with the cross products make problems since you can multiply very small values and I find it difficult to choose a proper epsilon. Any suggestions to make the tests more robust? [Edited by - DonDickieD on March 4, 2008 8:49:36 AM]

Share this post


Link to post
Share on other sites
You can use the cross product, but I think that a more efficient way (if I understood what you want correctly) will be this way:
Say you have the vectors v = (v1, v2, v3) and u = (u1, u2, u3).
Define 3 variables, a, b and c. a would be (v1 / u1), b = (v2 / u2) and c = (v3 / u3). If the vectors are collinear, then a should be equal to b and c (or the difference smaller then epsilon, which could be something like 0.001, depends on the accuracy you need).

I think it would be faster than the cross product because you don't need to determine the length of a vector, or to make a lot of subtractions and multiplications like in the cross product.

Share this post


Link to post
Share on other sites
Yes, I though about this. But there are some special cases. Basically you must check for divisions by zero and also you can get 0 / 0 which is basically a wildcard since you don't need to check this element then at all. Because of all the branches I doubt that this is more efficient or robust...

Share this post


Link to post
Share on other sites
Actually, when having 0s it's much easier. If u1 = 0 then v1 must be 0 for them to be collinear, and vice versa - you can "get rid of" a variable and a series of 'if' checks. If you see that u1 = 0 and v1 <> 0 then you know for sure that they're not collinear.

Share this post


Link to post
Share on other sites
Why not use dot product instead? If the dot product is equal to the product of the lengths of the vectors, then the vectors will be parallel (vectors don't have position, so they aren't said to be collinear).

(u dot v) / (length(u) * length(v)) > 1 - epsilon

This is the same idea as what you had, but here epsilon takes into account the magnitudes of the vectors. The expression above can be greatly simplified, obviously; if you want, you can perform the whole thing using only multiplication.

I'd wager that a branching structure like ofireps suggested could improve the speed of this test further.

Share this post


Link to post
Share on other sites

This topic is 3568 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this