Rotation matrix that minimizes distance

Question

Let's say I have two points in 3D space (a and b) and a fixed axis/unit vector called n.

I want to create a rotation matrix that minimizes the euclidan distance between point a (unrotated) and the rotated point b.

E.g:

 Q := matrix_from_axis_and_angle (n, alpha);

 find the unknown alpha that minimizes sqrt(|a - b*Q|)

Btw - If a solution/algorithm can be easier expressed with unit-quaternions go ahead and use them. I just used matrices to formulate my question because they're more widely used.

---

Oh - I know there are some degenerated cases ( a or b lying exactly in line with n ect.) These can be ignored. I'm just looking for the case where a single solution can be calculated.

Answer 1

I think you can rephrase the question to:

what is the distance from a point to a 2d circle in 3d space.

the answer can be found here

so the steps needed are as following:

• rotating the point b around a vector n gives you a 2d circle in 3d space
• using the above, find the distance to that circle (and the point on the circle)
• the point on the circle is the rotated point b you are looking for.
• deduce the rotated angle

...or something ;^)

Answer 2

The distance will be minimized when the vector from a to the line along n lines up with the vector from b to the line along n.

Project a and b into the plane perpendicular to n and solve the problem in 2 dimensions. The rotation you get there is the rotation you need to minimize the distance.

Answer 3

sounds fairly easy. Assume unit vector n implies rotation around a line parallel to n through point x0. If x0 != the origin, translate the coordinate system by -x0 to get points a' and b' relative to new coordinate system origin 0, and use those 2 points instead of a and b.

1) calculate vector ry = n x a

2) calculate unit vector uy = unit vector in direction ry

3) calculate unit vector ux = uy x n

You now have a triplet of mutually perpendicular unit vectors ux, uy, and n, which form a right-handed coordinate system. It can be shown that:

 a = dot(a,n) * n  +  dot(a,ux) * ux

This is because unit vector uy is parallel to ry which is perpendicular to both a and n. (from step 1)

4) Calculate components of b along unit vectors ux, uy. a's components are (ax,0) where ax = dot(a,ux). b's components are (bx,by) where bx = dot(b,ux), by = dot(b,uy). Because of the right-handed coordinate system, ax is always positive so you don't actually need to calculate it.

5) Calculate theta = atan2(by, bx).

Your rotation matrix is the one which rotates by angle -theta relative to coordinate system (ux,uy,n) around the n-axis.

This yields degenerate answers if a is parallel to n (steps 1 and 2) or if b is parallel to n (steps 4, 5).

Answer 4

Let P be the plane that is perpendicular to n. We can find the projection of a into the P-plane, (and similarly for b):

a' = a - (dot(a,n)) n 
b' = b - (dot(b,n)) n

where dot(a,n) is the dot-product of a and n

a' and b' lie in the P-plane.

We've now reduced the problem to 2 dimensions. Yay!

The angle (of rotation) between a' and b' equals the angle (of rotation) needed to swing b around the n-axis so as to be closest to a. (Think about the shadows b would cast on the P-plane).

The angle between a' and b' is easy to find:

dot(a',b') = |a'| * |b'| * cos(theta)

Solve for theta.

Now you can find the rotation matrix given theta and n here: http://en.wikipedia.org/wiki/Rotation%5Fmatrix

Jason S rightly points out that once you know theta, you must still decide to rotate b clockwise or counterclockwise about the n-axis.

The quantity, dot((a x b),n), will be a positive quantity if (a x b) lies in the same direction as n, and negative if (a x b) lies in the opposite direction. (It is never zero as long as neither a nor b is collinear with n.)

If (a x b) lies in the same direction as n, then b has to be rotated clockwise by the angle theta about the n-axis.

If (a x b) lies in the opposite direction, then b has to be rotated clockwise by the angle -theta about the n-axis.