Kessells_SR@cc.curtin.edu.au (12/12/90)
Problem : Given a set of 3D points what is the best plane of fit to them. It is needed to provide a good projection plane for the points. Any comments or code would be greatly appreciated, Thanks ! Michael Evans ------------------------------------------------------ Aussie Post: Michael Evans Internet: TKESSELLS01@cc.curtin.edu.au ACSnet: TKESSELLS01@cc.cut.oz.au Bitnet: TKESSELLS01%cc.curtin.edu.au@cunyvm.bitnet UUCP: uunet!munnari.oz!cc.curtin.edu.au!TKESSELLS01
jroth@allvax.enet.dec.com (Jim Roth) (12/13/90)
In article <5110.276634ff@cc.curtin.edu.au>, Kessells_SR@cc.curtin.edu.au writes... > >Problem : > > Given a set of 3D points what is the best plane of fit to them. > >It is needed to provide a good projection plane for the points. Any comments >or code would be greatly appreciated, Thanks ! One approach would be to consider the points as point-masses, and compute the eigenvectors of the inertia matrix (or covariance) matrix. Then the plane will pass thru the centroid of the points with a normal vector equal to the eigenvector belonging to the largest eigenvalue. You can compute the eigenvalues/vectors of such a low dimensional symmetric matrix easily with a Jacobi routine, hard wired for 3 dimensions for speed, out of Numerical Recipes or EISPACK... This assumes simple-minded Gaussian distributions of errors and so on, but is not a bad way to go if the points are not in any kind of order. This statistical idea goes back to the turn of the century - there is an old paper "On lines and planes of closest fit to systems of points in space", by K. Pearson, Phil Mag (don't have the date but could look it up if you want.) Another approach if the points form the oriented boundary of a polygon (or even a boundary set if the poly has holes) would be to compute the cross products round the boundary edges, accumulate the resulting vector, and use that as the normal. This is faster than the centroid idea. If you have lots of cases where there are 3 or 4 points, it would be worth special casing these for speed. - Jim
root@fstc-chville.army.mil (Operator) (12/14/90)
Kessells_SR@cc.curtin.edu.au writes: >Problem : > Given a set of 3D points what is the best plane of fit to them. Mike... From Ballard and Brown page 476 or Foley and VanDam page 512: given three points (x,y,z), form the equation _ _ _ _ _ _ | x1 y1 z1 1 | | A | | 0 | | x2 y2 z2 1 | | B | | 0 | | x3 y3 z3 1 | | C | = | 0 | | 0 0 0 1 | | D | | 1 | _ _ _ _ _ _ Invert the first matrix, solve for [ABCD]. The equation of the plane is Ax+By+Cz+D=0. See the references for cases when the large matrix doesn't invert. Brian boyter@fstc-chville.army.mil