Least Squares Plane

A plane in 3D space may be defined by

Ax+By+Cz+D=0.

where A, B, and C furnish the components of the normal of the plane. In other words, the plane normal is given by N=(A,B,C). Assume the above plane is normalized (i.e., N is a unit vector). Then, the distance between a point p_i=(x_i,y_i,z_i) and the plane is given by

di = Axi+Byi+Czi-D.

For a given set of points p_i (i=1,2,3... n), our task is to find a plane such that the distance between p_i and the plane is minimized in some fashion. After having obtained the definition of the plane, we may compute the actual distance between p_i and the plane with i=0,1,2,...,n and compare it with the given tolerance to determine whether all the points are on the plane.

Since d_i may be positive or negative, an appropriate minimization of d_i is the least squares approximation, which is equivalent to finding A, B, C, and D such that

f(A,B,C,D)= n å i=1  di2= n å i=1  (Axi+Byi+Czi-D)2

is minimized. Accordingly, we want to solve the following system of liner equations:

       [(df)/(dA)]=2å_i=1ⁿ[Ax_i+By_i+Cz_i-D]x_i=0

       [(df)/(dB)]=2å_i=1ⁿ[Ax_i+By_i+Cz_i-D]y_i=0

       [(df)/(dC)]=2å_i=1ⁿ[Ax_i+By_i+Cz_i-D]z_i=0

       [(df)/(dD)]=2å_i=1ⁿ[Ax_i+By_i+Cz_i-D]=0

From df/dD=0, we have D=Ax_c+By_c+Cz_c where

xc= n å i=0  xi n ,    yc= n å i=0  yi n ,    zc= n å i=0  zi n .

The above relation shows that the least squares plane passes through the centroid (or the center of mass) of the points.

In order to simplify computation, we subtract the center of mass, (x_c,y_c,z_c), from each point. In this case, the least squares plane will pass through the origin. Accordingly, D=0 and f = å_i=1ⁿ[A(x_i-x_c)+B(y_i-y_c)+C(z_i-z_c)]. Therefore, we have

       [(df)/(dA)]=å_i=1ⁿ[A(x_i-x_c)²+B(y_i-y_c)(x_i-x_c)+ C(z_i-z_c)(x_i-x_c)]=0

       [(df)/(dB)]=å_i=1ⁿ[A(x_i-x_c)(y_i-y_c)+B(y_i-y_c)²+ C(z_i-z_c)(y_i-y_c)]=0

       [(df)/(dC)]=å_i=1ⁿ[A(x_i-x_c)(z_i-z_c)+B(y_i-y_c)(z_i-z_c)+ C(z_i-z_c)²]=0

Let

       a₀₀=å_i=1ⁿ(x_i-x_c)²,

       a₁₁=å_i=1ⁿ(y_i-y_c)²,

       a₂₂=å_i=1ⁿ(z_i-z_c)²,

       a₀₁=a₁₀=å_i=1ⁿ(x_i-x_c)(y_i-y_c),

       a₀₂=a₂₀=å_i=1ⁿ(x_i-x_c)(z_i-z_c), and

       a₁₂=a₂₁=å_i=1ⁿ(y_i-y_c)(z_i-z_c).

Then, the desired A, B, and C are obtained by solving

æ ç ç ç è a00 a01 a02 a10 a11 a12 a20 a21 a22 ö ÷ ÷ ÷ ø æ ç ç ç è A B C ö ÷ ÷ ÷ ø =0.

The above system has a trivial solution A=B=C=0. For a non-trivial solution, we may require A²+B²+D²=1. With this constraint, it is readily seen that solution to the above equation is an eigenvalue problem (Computation of three eigenvalues and eignevectors is well documented in any linear algebra book and hence not discussed here). The three eignevectors are mutually orthogonal and define three sets of A, B, and C. These three sets represent the best, intermediate, and worst planes. In our case, we want to choose the eignevector associated with the smallest eignevalue (Note: The eignevalue is the sum of squared distances). If all three eignevalues are the same, then the given points are either degenerate or symmetric.