Best Fitting Plane given a Set of Points

Nothing more to explain. I just don't know how to find the best fitting plane given a set of $N$ points in a $3D$ space. I then have to write the corresponding algorithm. Thank you ;)

• There is plenty more to explain. There are many different measures of how well a plane fits given data, and different measures give rise to different "best" fitting planes. So you had best tell us what you have in mind as your measure of how well a given plane fits some given data. – Gerry Myerson Jan 15 '12 at 21:02
• I'm sorry but I wish I could tell you more. But I know just a bit. Let's say that the set of Points I have (over a 100) already look like a plane, I mean, they are displayed as a plane but not perfectly. "Obtain the symmetry plane A by fitting it on the set of points B.." That's all I have to do. They don't say anything more. – G4bri3l Jan 16 '12 at 9:20
• You hadn't mentioned the symmetry part before -- do you know what that's referring to? – joriki Jan 16 '12 at 9:53
• The "symmetry plane" may confuse you. I have this set of points that represents the symmetry plane (but it could be any plane), but I actually don't know the equation of this plane (and I need it). So I presumed that the only way I can find this equation is finding the best fitting plane given this set of points. I'm sorry if I'm not explaining the whole thing properly. – G4bri3l Jan 16 '12 at 10:23
• Let's look at a simpler problem. Say you have a bunch of points in 2 dimensions that almost lie along a line, but not quite, and you want to find the line that fits those points the best. You could draw a line, then draw vertical line segments from each point to the line, and add up the lengths of all those line segments, and ask for the line that makes that sum as small as possible. But you could draw horizontal line segments instead, and you might get a different answer by minimizing the sum of those lengths. Or you could draw line segments perpendicular to the line. Continued... – Gerry Myerson Jan 16 '12 at 11:23

Subtract out the centroid, form a $3\times N$ matrix $\mathbf X$ out of the resulting coordinates and calculate its singular value decomposition. The normal vector of the best-fitting plane is the left singular vector corresponding to the least singular value. See this answer for an explanation why this is numerically preferable to calculating the eigenvector of $\mathbf X\mathbf X^\top$ corresponding to the least eigenvalue.

• I'll give it a try. I was thinking, what if I use the PCA algorithm instead ? Because my set of points are always going to be displayed as a plane, so I just need to find the equation. With PCA I can find the most relevant directions and then easily find a plane. Am I thinking wrong ? – G4bri3l Jan 16 '12 at 9:38
• @G4bri3l: Did you follow the link? – joriki Jan 16 '12 at 9:54
• Yeah I saw the link. But since I already implemented the PCA algorithm and I actually don't really care if it's numerically notpreferable, maybe I should use it. But I'll probably find an already implemented algorithm for the SVD so, I should use that instead of PCA. Thank you @joriki, this was really helpful! – G4bri3l Jan 16 '12 at 10:40
• How can I use this method for the best fitting line (3d). I think I'm supposed to use the right singular vector corresponding to the largest singular value, but how am I using it to find the best fitting line ? – G4bri3l Jan 17 '12 at 16:41
• @G4bri3l: I'm not sure I understand that question. The way I've defined $\mathbf X$, its right-singular vectors are $N$-dimensional, so I don't see how they could be used to find the best-fitting line. It's the left singular vectors that are $3$-dimensional, and indeed the left singular vector $u$ corresponding to the largest singular value gives the direction of the best-fitting line. Remember that $\mathbf X$ contains the coordinates with the centroid $c$ subtracted out, so the equation for the best-fitting line is $c+\lambda u$. – joriki Jan 17 '12 at 17:18

A simple least squares solution should do the trick.

The equation for a plane is: $ax + by + c = z$. So set up matrices like this with all your data:

$$\begin{bmatrix} x_0 & y_0 & 1 \\ x_1 & y_1 & 1 \\ &... \\ x_n & y_n & 1 \\ \end{bmatrix} \begin{bmatrix} a \\ b \\ c \end{bmatrix} = \begin{bmatrix} z_0 \\ z_1 \\ ... \\ z_n \end{bmatrix}$$ In other words:

$$Ax = B$$

Now solve for $x$ which are your coefficients. But since (I assume) you have more than 3 points, the system is over-determined so you need to use the left pseudo inverse: $A^+ = (A^T A)^{-1} A^T$. So the answer is: $$\begin{bmatrix} a \\ b \\ c \end{bmatrix} = (A^T A)^{-1} A^T B$$

And here is some simple Python code with an example:

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np

N_POINTS = 10
TARGET_X_SLOPE = 2
TARGET_y_SLOPE = 3
TARGET_OFFSET  = 5
EXTENTS = 5
NOISE = 5

# create random data
xs = [np.random.uniform(2*EXTENTS)-EXTENTS for i in range(N_POINTS)]
ys = [np.random.uniform(2*EXTENTS)-EXTENTS for i in range(N_POINTS)]
zs = []
for i in range(N_POINTS):
zs.append(xs[i]*TARGET_X_SLOPE + \
ys[i]*TARGET_y_SLOPE + \
TARGET_OFFSET + np.random.normal(scale=NOISE))

# plot raw data
plt.figure()
ax = plt.subplot(111, projection='3d')
ax.scatter(xs, ys, zs, color='b')

# do fit
tmp_A = []
tmp_b = []
for i in range(len(xs)):
tmp_A.append([xs[i], ys[i], 1])
tmp_b.append(zs[i])
b = np.matrix(tmp_b).T
A = np.matrix(tmp_A)
fit = (A.T * A).I * A.T * b
errors = b - A * fit
residual = np.linalg.norm(errors)

print "solution:"
print "%f x + %f y + %f = z" % (fit, fit, fit)
print "errors:"
print errors
print "residual:"
print residual

# plot plane
xlim = ax.get_xlim()
ylim = ax.get_ylim()
X,Y = np.meshgrid(np.arange(xlim, xlim),
np.arange(ylim, ylim))
Z = np.zeros(X.shape)
for r in range(X.shape):
for c in range(X.shape):
Z[r,c] = fit * X[r,c] + fit * Y[r,c] + fit
ax.plot_wireframe(X,Y,Z, color='k')

ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('z')
plt.show() • Am I correct to interpret that this method will solve for the plane that minimizes the vertical (ie: z) distance and not the perpendicular distance? – Gabriel Nov 8 '17 at 23:03
• Yes, it minimizes vertical distance. – Ben Nov 9 '17 at 0:00
• Thank you very much for clarifying this Ben (and for the answer) If you have the time, I have a very similar question here (using Singular-Value Decomposition) that is giving me trouble. – Gabriel Nov 9 '17 at 18:36

Considering a plane of equation $Ax+By+Cz=0$ and a point of coordinates $(x_i,y_i,z_i)$, the distance is given by $$d_i=\pm\frac{Ax_i+By_i+Cz_i}{\sqrt{A^2+B^2+C^2}}$$ and I suppose that you want to minimize $$F=\sum_{i=1}^n d_i^2=\sum_{i=1}^n\frac{(Ax_i+By_i+Cz_i)^2}{{A^2+B^2+C^2}}$$ Setting $C=1$, we then need to minimize with respect to $A,B$ $$F=\sum_{i=1}^n\frac{(Ax_i+By_i+z_i)^2}{{A^2+B^2+1}}$$ Taking derivatives $$F'_A=\sum _{i=1}^n \left(\frac{2 x_i (A x_i+B y_i+z_i)}{A^2+B^2+1}-\frac{2 A (A x_i+B y_i+z_i)^2}{\left(A^2+B^2+1\right)^2}\right)$$ $$F'_B=\sum _{i=1}^n \left(\frac{2 y_i (A x_i+B y_i+z_i)}{A^2+B^2+1}-\frac{2 B (A x_i+B y_i+z_i)^2}{\left(A^2+B^2+1\right)^2}\right)$$ Since we shall set these derivatives equal to $0$, the equations can be simplified to $$\sum _{i=1}^n \left({ x_i (A x_i+B y_i+z_i)}-\frac{ A (A x_i+B y_i+z_i)^2}{\left(A^2+B^2+1\right)}\right)=0$$ $$\sum _{i=1}^n \left({ y_i (A x_i+B y_i+z_i)}-\frac{ B (A x_i+B y_i+z_i)^2}{\left(A^2+B^2+1\right)}\right)=0$$ whic are nonlinear with respect to the parameters $A,B$; then, good estimates are required since you will probably use Newton-Raphson for polishing the solutions.

These can be obtained making first a multilinear regression (with no intercept in your cas) $$z=\alpha x+\beta y$$ and use $A=-\alpha$ and $B=-\beta$ for starting the iterative process. The values are given by $$A=-\frac{\text{Sxy} \,\text{Syz}-\text{Sxz}\, \text{Syy}}{\text{Sxy}^2-\text{Sxx}\, \text{Syy}}\qquad B=-\frac{\text{Sxy}\, \text{Sxz}-\text{Sxx}\, \text{Syz}}{\text{Sxy}^2-\text{Sxx}\, \text{Syy}}$$

For illustration purposes, let me consider the following data $$\left( \begin{array}{ccc} x & y & z \\ 1 & 1 & 9 \\ 1 & 2 & 14 \\ 1 & 3 & 20 \\ 2 & 1 & 11 \\ 2 & 2 & 17 \\ 2 & 3 & 23 \\ 3 & 1 & 15 \\ 3 & 2 & 20 \\ 3 & 3 & 26 \end{array} \right)$$

The preliminary step gives $z=2.97436 x+5.64103 y$ and solving the rigorous equations converges to $A=-2.97075$, $B=-5.64702$ which are quite close to the estimates (because of small errors).

• In your example, the equation of the plane $z=Ax+By$ is carried out with respect to the criteria of the least square orthogonal distances between the points and the plane. I agree with your result. But, they are only two adjustable parameters $A,B$ because the origin $(0,0,0)$ is supposed to be on the plan. This is an additional condition. If we consider the more general equation of the plan $z=Ax+By+C$ the three parameters problem should lead to a better fitting with lower mean square deviation. – JJacquelin Feb 12 '16 at 15:18

In order to complete the Claude Leibovici's answer :

With the numerical example proposed by Claude Leibovici who computed the parameters of a fitted plane $\quad z=Ax+By\quad$, the fitting of the plane $\quad Z=\alpha X+\beta Y+\gamma\quad$ can be carried out thanks to the principal components method (as suggested by joriki).

The theory can be found in many books. A synopsis is given pages 24-25 in the paper: https://fr.scribd.com/doc/31477970/Regressions-et-trajectoires-3D

The symbols used below correspond to those in the formulas from the referenced paper. 