From: ptitjean@ccr.jussieu.fr (Michel PETITJEAN)
Subject: Re: Best fit algorithm
Date: 25 Jan 2001 13:04:35 +0100
Newsgroups: sci.math.num-analysis
Summary: Finding Euclidean motions to match as many points as possible

Ref: <3a6d3f19$0$8789$4dbef881@businessnews.de.uu.net>
     <942h5k$oev$1@news.inet.tele.dk>
     <944gau$85g$1@sun27.hrz.tu-darmstadt.de> 
     <944i5b$sr6$1@news.inet.tele.dk>

Chemists have also this problem. Having n1 3D-points and n2
3D-points, find the largest common 3D subset (n3 points).
The correspondence between the n3 points in set 1 and the
n3 points in set 2 is computed (n3 smaller or equal
to n1 or n2; n3 is computed). Rotation and translation
are computed too. See the CSR software:
M.Petitjean,
Interactive Maximal Common 3D Substructure Searching with the
Combined SDM/RMS Algorithm, Comp. & Chem. 1998,22(6),463-465.

When the pairwise correspondence is known (n1=n2=n), the
least sqare method is easy to implement (e.g. see appendix 
in my paper in . Math. Phys., 1999,40(9),4587-4595),
but this is a much simpler situation..

Michel Petitjean,                     Email: petitjean@itodys.jussieu.fr
ITODYS (CNRS, ESA 7086)                      ptitjean@ccr.jussieu.fr

>"Mads Paulin" <paulin@mip.sdu.dk> schrieb im Newsbeitrag
>news:944i5b$sr6$1@news.inet.tele.dk...
>> My model is made up of a set of 3D points. The data I have to fit to the
>> model is another set of 3D points. The data set is rotated and translated in
>> an unknown way (the rotation and the translation is the final result of my
>> algorithm) compared to the model set. If i can make the best fit of the data
>> set to the model set i can determine correspondances between points in the
>> model and points in the data set and thereby calculate the desired
>> translation and rotation.
>> ...