[Math] least square solution for obtaining a line 3d by intersecting many planes

differential-geometrygeometrysolid-geometryvector-spaces

If I have been given 4 planes and I know only a point (just a point lie on the plane e.g. o1,o2, o3 & o4) and normal vector of each plane (n1, n2, n3 & n4). Then, by intersecting all 4 (or more) planes, if this makes a line 3D, then how it would be computed using least square method. Assume my least square fitted best intersection line as the red line in the picture.

enter image description here

Please, show me the step by step solution to get this. Showing this in matrix form is helpful for me as I want to implement this in the c++ programming environment.
Thanks in advance.

Note: if I take 2 planes per time, then the intersection lines are not exactly collinear… there might be bit shift..So i want to get the best line which wold represent the intersection of all planes.

I have updated my original post little bit to more clear.

Best Answer

Suppose there are $m (m\geq 4)$ planes, for plane number $k$ we know a point $\mathbf{x}_k = (x_{k,1},x_{k,2},x_{k,3})$ on the plane, and the unit normal vector for plane number $k$ is $\mathbf{n}_k$.

Here I am not sure whether you mean by "a point for each plane", or "a common point for all planes", both are discussed.


If we assume that all planes pass through point $\mathbf{x}_0$. Then this line can be represented using this point $\mathbf{x}_0$ and a direction $\mathbf{b} = (b_1,b_2,b_3)$ $$ \mathbf{x} = \mathbf{x}_0 + t\mathbf{b} \quad\text{ for } t\in \mathbb{R} $$ Then the problem does not need least-square treatment at all, as we are not solving an overdetermined system, $\mathbf{b}$ can be obtained simply by cross product any two normals: $$ \mathbf{b} = \mathbf{n}_1\times\mathbf{n}_2, \tag{1} $$ where $\times$ is the cross product of vectors. Because the normal vectors of all the planes are coplanar (thus the planes intersect at exactly one line), $\mathbf{b}\perp \mathbf{n}_1, \mathbf{n}_2,\ldots, \mathbf{n}_m$. And we are done.


If we only know a point for each plane, and we do not know if they all passing through one common line. Things get more complicated. The least square problem may not be well-posed. We want this line being perpendicular to every plane (as much as possible), and passing through a point that has the minimal distance to all the planes. The equation system for $\mathbf{x} = (x_1,x_2,x_3)$ is: $$ \mathrm{dist}(\mathbf{x},P_k) = |\mathbf{n}_k \cdot (\mathbf{x} - \mathbf{x}_k )| = 0 $$ written in matrix form $$ \mathbf{N}\mathbf{x}:= \begin{pmatrix}n_{1,1} &n_{1,2} &n_{1,3} \\ n_{2,1} &n_{2,2} &n_{2,3} \\ \vdots&\vdots&\vdots \\ n_{m,1} &n_{m,2} &n_{m,3}\end{pmatrix}\begin{pmatrix}x_1 \\x_2 \\x_3\end{pmatrix} = \mathbf{y} := \begin{pmatrix}\mathbf{n}_1 \cdot \mathbf{x}_1 \\ \mathbf{n}_2 \cdot \mathbf{x}_2 \\ \vdots \\ \mathbf{n}_m \cdot \mathbf{x}_m\end{pmatrix}\tag{2} $$ where $\mathbf{N}$ is an $m\times 3$ matrix, which is basically the list of all the normal vectors row by row. The least square formulation for problem (2) is to minimize: $$ \min_{\mathbf{x}} \|\mathbf{N}\mathbf{x}-\mathbf{y}\|, $$ where the norm is just Euclidean norm, the solution is the point $\mathbf{x}_0$ satisfying: $$ \mathbf{N}^{T}\mathbf{N}\mathbf{x}_0 = \mathbf{N}^{T}\mathbf{y}. \tag{$\dagger$} $$ $(\dagger)$ is the first matrix equation you wanna solve. After we obtain this $\mathbf{x}_0$, we wanna find a $\mathbf{b}$ such that:

  • Either if all these planes intersecting at 1 line, we can find this $\mathbf{b}$ exactly for this line.

  • Or if they do not intersect at 1 line, but every two of them intersect at 1 line (no parallel planes, you can rule out parallel planes by checking same normals or normals with opposite signs but same in each component). We use least square to find it.

For the first case, we know that $\mathbf{b}$ satisfies: $$ \mathbf{b}\cdot \mathbf{n}_j = 0 $$ for every plane number $j$, because the line being on every plane means it is perpendicular to every normal vector $ \mathbf{n}_j $. In this case, simply computing (1) is enough.

For the second case, the least square system produced by $\mathbf{b}\cdot \mathbf{n}_j = 0$ is: $$ \min_{\mathbf{b}} \|\mathbf{N}\mathbf{b}\|, $$ and the solution is zero if these planes do not intersect. One possible way is simply compute the mean of $\mathbf{n}_i\times\mathbf{n}_j$, which is the intersecting line vector for every two of the planes, and set this mean as $\mathbf{b}$. Another way(essentially the same) is more least square'ish is try to solve the minimization: $$ \min_{\mathbf{b}} \sum_{i,j}\|\mathbf{b} - \mathbf{n}_i\times\mathbf{n}_j\|^2, $$ so that the resulting $\mathbf{b}$ is the closest line parallel to all intersecting line vector of every two of the planes in least square sense. In this minimization, you need to be careful with the normal direction because of $\mathbf{n}_i\times\mathbf{n}_j = -\mathbf{n}_j\times\mathbf{n}_i$, you wanna make sure all the intersecting line vector be about the same direction, i.e., $(\mathbf{n}_i\times\mathbf{n}_j)\cdot (\mathbf{n}_k\times\mathbf{n}_l) \geq 0$. The final minimizer is the mean of $\mathbf{n}_i\times\mathbf{n}_j$, for the case of four planes: $$ \begin{aligned} \mathbf{b} =& (\mathbf{n}_1\times\mathbf{n}_2 + \mathbf{n}_1\times\mathbf{n}_3 + \mathbf{n}_1\times\mathbf{n}_4 \\ &+\mathbf{n}_2\times\mathbf{n}_3 + \mathbf{n}_2\times\mathbf{n}_4 \\ &+ \mathbf{n}_3\times\mathbf{n}_4)/6, \end{aligned} $$ if we assume looking from the intersecting line perspective, the direction pointed by $\mathbf{n}_1$, $\mathbf{n}_2$, $\mathbf{n}_3$, to $\mathbf{n}_4$ is rotating counterclockwisely. For example in your picture you wanna make the fourth normal vector pointing the opposite direction.


For even larger data set, please refer to: http://en.wikipedia.org/wiki/Principal_component_analysis

Related Question