Nearest Neighbours using Quaternions

Given a quaternion value, I开发者_开发技巧 would like to find its nearest neighbour in a set of quaternions. To do this, I clearly need a way to compare the "distance" between two quaternions. What distance representation is needed for such a comparison and how is it computed?

Thanks,

Josh

This is an old question, but it seemed to need a little more answer. If the quaternions are unit-length quaternions being used to represent rotations, then Euclidean distance will give some funny results because quaternions provide 2x redundant representation of rotation space; i.e., a quaternion and its negation represent the same orientation. In this case, the correct distance metric is the angle between the quaternions, constrained to fall within [0,pi/2]:

theta = acos(q1.w*q2.w + q1.x*q2.x + q1.y*q2.y + q1.z*q2.z);
if (theta>pi/2) theta = pi - theta;

Is your quaternion just a point in 3D space with an orientation?

Then the distance between two quaternions x1,y1,z1,w1 and x2,y2,x2,w2 is given by:

distance = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2), assuming that the w component is used for orientation. I.e. this is the same as the distance between two 3D points.

Is your quaternion a point in 4D space?

Then the distance between them is given by:

distance = sqrt((x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 + (w1-w2)^2).

Which is just the extension to 4D space. This euclidean distance formula works in any number of dimensions.

This really depends on what you use your quaternions for. A simple distance measure would be the absolute value of their difference.

If x = a + b i + c j + d k y = e + f i + g j + h k

than the Euclidean distance would be

 |x-y| = sqrt( (a-e)² + (b-f)² + (c-g)² + (d-h)² )

If "distance" you mean the shortest arc rotation between 2 orientations , than simple Euclidean distance is ok (L2 or norm2).

because angle between orientations can be written as

theta = acos(q1.w*q2.w + q1.x*q2.x + q1.y*q2.y + q1.z*q2.z);

Than, the bigger L2, the bigger distance.

NOTE: all quaternions before query should be negated if provide negative dot product. Than you can use usual KNN match to speedup your queries.