Least squares line of intersection for multiple planes

Question

I'm working on a problem where I have many (between 500-2000) planes which theoretically all pass through a given line. These planes are all compactly described as a vector $\vec Q$, such that

$x = \vec Q \cdot (1,\,y,\,z)$.

Since I want for my application to express the line as

$\vec L (t)= \vec O + \vec Dt$,

where $\vec O$ lies on the $y=0$ plane, it is simple to find the point $\vec O$. The problem reduces to 2D least squares line intersection. (All planes are guaranteed to intersect $y=0$.) The only problem that remains is then to find the best-fit direction of intersection $\vec D$ for all planes.

I know that for two given planes with normals $\vec n_1$ and $\vec n_2$ the line of intersection is parallel to $\vec n_1 \times \vec n_2$. However, I do not know how to apply this knowledge to least squares. My software makes use of a matrix library so matrix solutions would be best.

How can I find the direction $\vec D$ of my line?

Answer 1

The general equation of a plane in 3-D is given by $$\mathbf{(p-p_0).n}=0$$ where $\mathbf{p}$ is any general point on the plane, and $\mathbf{p_0}$ is any known point on the plane. $\mathbf{n}$ is a vector normal to the plane.

The equation of a line is given by $$\mathbf{p = l_0+}t\mathbf{l} $$ where $\mathbf{l_0}$ is any point on the line.

If the line lies in the plane, it must satisfy two conditions-

1. It must be perpendicular to the normal to the plane i.e. $\mathbf{l.n}=0$

2. $\mathbf{l_0}$ must lie in the plane i.e. satisfy the plane's equation. So, $\mathbf{(l_0-p_0).n} = 0$

You can calculate $\mathbf{p_0,l_0}$ very easily with the information you have. $\mathbf{p_0}$ can be calculated by choosing any two of $x,y,z$ and finding the third to satisfy the equation of the plane. $\mathbf{l_0}$ is precisely $\vec O$ that you already know. You can use them to cross-check whether the fit is good or not. But they do not depend on $\mathbf{l}$. So, they are secondary, and may be used as a sanity check later on.

Suppose you are given the equation of the line as $ax+by+cx+d = 0$. You can recast it as $[(x,y,z)-\mathbf{p_0}].(a,b,c)$. So, $(a,b,c)$ is your normal vector.

Suppose you have $m$ planes with normals $\mathbf{n_1,n_2,\ldots,n_m}$. Then, your overall constraints are $$\mathbf{l.n_1} = 0 \\ \mathbf{l.n_2} = 0 \\ \ldots \\\mathbf{l.n_m}=0$$.

It is a system of linear equations with 3 variables and $m$ equations. You need to find out $\mathbf{l}$, which can be found up to a constant factor by the standard least squares method, provided $m>3$, which should not be a worry for you. If you code carefully enough, you can implement all of it in matrix terms.

Hope it helps.