Calculate the center point of multiple lines

Question

I have $n\ge3$ lines $L_i$ given in 3D Space.

How do I calculate a point $P$ with minimal $\sum_{i=1}^{n} distance(L_i, P)$?

Answer 1

Let's call the lines $$\ell_1:=\{\vec u_1\lambda+\vec v_1\mid\lambda\in\mathbb{R}\}$$ $$\ell_2:=\{\vec u_2\lambda+\vec v_2\mid\lambda\in\mathbb{R}\}$$ $$\ell_3:=\{\vec u_3\lambda+\vec v_3\mid\lambda\in\mathbb{R}\}$$ Where $\vec u_i,\ \vec v_i\in\mathbb{R}^3$.

For a point $p\in\mathbb{R}^3$, the distance between $p$ and $\ell_i$ is, due to classical results, $$ d_i=\frac{||(\vec p-\vec v_i)\times\vec u_i||}{||\vec u_i||} $$ If $\vec p=\begin{pmatrix}p_x\\p_y\\p_z\end{pmatrix},\ \vec v_i=\begin{pmatrix}v_{xi}\\v_{yi}\\v_{zi}\end{pmatrix},\ \vec u_i=\begin{pmatrix}u_{xi}\\u_{yi}\\u_{zi}\end{pmatrix}$, then $$d_i=\frac{\left|\left|\begin{pmatrix}p_x-v_{xi}\\p_y-v_{yi}\\p_z-v_{zi}\end{pmatrix}\times\begin{pmatrix}u_{xi}\\u_{yi}\\u_{zi}\end{pmatrix}\right|\right|}{\left|\left|\begin{pmatrix}u_{xi}\\u_{yi}\\u_{zi}\end{pmatrix}\right|\right|}=\frac{\left|\left|\begin{pmatrix}u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi})\\u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi})\\u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi})\end{pmatrix}\right|\right|}{\sqrt{u_{xi}^2+u_{yi}^2+u_{zi}^2}}$$

$$ d_i=\sqrt{\frac{(u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))^2+(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))^2+(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))^2}{u_{xi}^2+u_{yi}^2+u_{zi}^2}} $$

$$ \frac{\partial d_i}{\partial \vec p}=\begin{pmatrix} \frac{-u_{zi}(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))+u_{yi}(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))}{\sqrt{\left((u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))^2+(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))^2+(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))^2\right)(u_{xi}^2+u_{yi}^2+u_{zi}^2)}} \\ \frac{u_{zi}(u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))-u_{xi}(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))}{\sqrt{\left((u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))^2+(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))^2+(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))^2\right)(u_{xi}^2+u_{yi}^2+u_{zi}^2)}} \\ \frac{u_{xi}(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))-u_{yi}(u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))}{\sqrt{\left((u_{zi}(p_y-v_{yi})-u_{yi}(p_z-v_{zi}))^2+(u_{xi}(p_z-v_{zi})-u_{zi}(p_x-v_{xi}))^2+(u_{yi}(p_x-v_{xi})-u_{xi}(p_y-v_{yi}))^2\right)(u_{xi}^2+u_{yi}^2+u_{zi}^2)}} \end{pmatrix} $$

Now, to minimize $\sum d_i$, we must solve for $\vec p$ such that $\sum_{i=1}^3 \frac{\partial d_i}{\partial \vec p}=0$. Sound fun to you? Me neither.