## [Algorithms] Best fit rigid body rotation for a set of points

 [Algorithms] Best fit rigid body rotation for a set of points From: Bill Baxter - 2005-04-30 23:47:15 Attachments: Message as HTML ```Does anyone know an algorithm for determining the rigid body transformation= =20 that best fits the motion of a set of N points? I.e. given a set of initial points p0 p1 ... pN, and their locations after= =20 some motion, q0 q1 ... qN, I want to find the rigid body transformation T(x= )=20 (rotation and translation only) that minimizes: Sum[i=3D0...N] ( || T(pi) - qi ||^2 ) The only thing I can think of is to treat it as a generic nonlinear=20 optimization problem, but it just seems like there should be something more= =20 efficient than that. =20 --Bill ```

 [Algorithms] Best fit rigid body rotation for a set of points From: Bill Baxter - 2005-04-30 23:47:15 Attachments: Message as HTML ```Does anyone know an algorithm for determining the rigid body transformation= =20 that best fits the motion of a set of N points? I.e. given a set of initial points p0 p1 ... pN, and their locations after= =20 some motion, q0 q1 ... qN, I want to find the rigid body transformation T(x= )=20 (rotation and translation only) that minimizes: Sum[i=3D0...N] ( || T(pi) - qi ||^2 ) The only thing I can think of is to treat it as a generic nonlinear=20 optimization problem, but it just seems like there should be something more= =20 efficient than that. =20 --Bill ```
 RE: [Algorithms] Best fit rigid body rotation for a set of points From: Tom Forsyth - 2005-05-01 00:14:40 ```Given any two points, you can find the rotation & translation that would exactly fit them. If the points are 0 and 1, then cross((P1-P2),(Q1-Q2)) will give you the axis of rotation & the sine of the angle. So you can = do that for all pairs and find the average, or something like that. Then you need to pick an origin that the rotation is about. Pick = anything - but using something like the centre-of-mass seems most intuitive, = transform the points P using that rotation, and see what additional translation is required to get them to Q. Again, find some sort of average of that. Note that what axis you perform your rotation _about_ determines what additional translation you require. In fact, IIRC, it is possible to = always pick a rotation axis such that the only translation required is _along_ = the axis of rotation. I think Casey Muratori can probably explain it better = than I can: http://www.funkytroll.com/ and search for "Periodic Loop Decomposition". TomF. -----Original Message----- From: gdalgorithms-list-admin@... [mailto:gdalgorithms-list-admin@...] On Behalf Of Bill Baxter Sent: 30 April 2005 16:47 To: gdalgorithms-list@... Subject: [Algorithms] Best fit rigid body rotation for a set of points Does anyone know an algorithm for determining the rigid body = transformation that best fits the motion of a set of N points? I.e. given a set of initial points p0 p1 ... pN, and their locations = after some motion, q0 q1 ... qN, I want to find the rigid body transformation = T(x) (rotation and translation only) that minimizes: Sum[i=3D0...N] ( || T(pi) - qi ||^2 ) The only thing I can think of is to treat it as a generic nonlinear optimization problem, but it just seems like there should be something = more efficient than that. --Bill ```