Wasn't it Rune who wrote:

>...or practically the same question formulated differently: If I have a
>bunch of random points, how can I find the normal of the plane that is as
>close as possible to as many as possible of the points? (The average
>distance from a point to the plane should be as small as possible.)

I'd try to extend the traditional line fitting technique from 2d into
3d. This technique actually minimises the average of the squares of the
distances, which produces a better looking fit than minimising the
average distances.

The 2d version:-

Calculate the mean of the x values, call it Mx.
Calculate the mean of the y values, call it My.
Calculate the mean of x^2, call it Mx2.
Calculate the mean of x*y, call it Mxy.

The best fit line y = A*x + B is then given by

A = (Mxy-Mx*My)/(Mx2-Mx*Mx)
B = My-A*Mx

[Example: three points <1,1> <2,1> <3,2>        ]
[ Mx  = (1+2+3)/3 = 2                           ]
[ My  = (1+1+2)/3 = 1.333                       ]
[ Mx2 = (1^2 + 2^2 + 3^2)/3 = (1+4+9)/3 = 4.667 ]
[ Mxy = (1*1 + 2*1 + 3*2)/3 = (1+2+6)/3 = 3     ]
[ A   = (3-2*1.333)/(4.667-2*1.333) = 0.167     ]
[ B   = 1.333-0.167*2 = 1                       ]
[ best line   y = 0.167*x + 1                   ]


Extending this into 3d is going to take a bit more thought.

-- 
Mike Williams
Gentleman of Leisure

Post a reply to this message