I would need to write an algorithm to find the closest point to a set of lines. These lines are infinite and are not parallel between each other.
Closest point means that point where the sum of the squared distances between the point and each of these lines is minimum.
Let's suppose a simple 2D case, where I have a line passing through $a_0 (1, 3)$ and $b_0 (2, 2)$ and another one through $a_1 (1, 1)$ and $b_1 (2, 2)$
I tried a couple of algorithms reading some other questions like this one but I couldn't get a valid result from the general formula
$$0 = \sum_{i=0}^m\vec c – \vec a_i – \vec d_i \frac{(\vec c – \vec a_i)\cdot \vec d_i}{\|\vec d_i\|^2}$$
I tried to set a system made by
$$
\left\{
\begin{array}{l}
0 = c_x-a_{x0}-d_{x0}\dfrac{(c_x-a_{x0})\cdot d_{x0}}{\|d_{x0}\|^2} + c_x-a_{x1}-d_{x1}\dfrac{(c_x-a_{x1})\cdot d_{x1}}{\|d_{x1}\|^2} \\
0 = c_y-a_{y0}-d_{y0}\dfrac{(c_y-a_{y0})\cdot d_{y0}}{\|d_{y0}\|^2} + c_y-a_{y1}-d_{y1}\dfrac{(c_y-a_{y1})\cdot d_{y1}}{\|d_{y1}\|^2}
\end{array}
\right.
$$
but I end up with
$$
\require{cancel}
\left\{
\begin{array}{l}
0= \cancel{c_x} – 1 – \cancel{c_x} + 1\\
0=\cancel{2c_y} -4 -\cancel{c_y} +3 – \cancel{c_y} -1
\end{array}
\right.
$$
So I guess I didn't apply properly the equations..
Then I also followed this other answer
I took two points on the line $$a_0 (1, 3)$$ and $$b_0 (2, 2)$$ subtracted to get a vector $$\vec v = b_0 – a_0 = (1, -1)$$ rotated by 90° $$(x, y) \to (-y, x)$$ that is $$(1, -1) \to (1, 1)$$ and divided by its length $$\sqrt{1^2+1^2} = \sqrt2$$ that is $$\left(\frac {1}{\sqrt2}, \frac {1}{\sqrt2}\right)$$ but I don't know how to get the formula
$$a_ix + b_iy+c_i$$
And then I also found this one, but it sounds too complicated..
How can I solve?
Best Answer
It took me a while but I realized how to do.
So, let's define the generic closest point as $$p (x_0, y_0)$$ and then let's call $d_i$ the generic $i_{th}$ distance from the $line_i$ to $p$
We have to find the point $p$ in order that sum of all the $n$ distancies $d_i$ is smallest as possible.
In order to do this, we need to sum all the squared distances $$\sum_{i=0}^n d_i^2$$
In the previous example with two lines $$ \begin{aligned} &L_0: \qquad x+y-4=0 \\ &L_1: \qquad x-y=0 \end{aligned}$$
We calculate the corresponding distances as following: $$\begin{aligned} d_0&=\dfrac{|x_0+y_0-4|}{\sqrt{1^2+1^2}}\\ d_1&=\dfrac{|x_0-y_0|}{\sqrt{1^2+(-1)^2}} \end{aligned}$$ so the sum of squared distances is: $$\sum_{i=0}^2 d_i =\left(\dfrac{|x_0+y_0-4|}{\sqrt{1^2+1^2}}\right)^2 + \left(\dfrac{|x_0-y_0|}{\sqrt{1^2+(-1)^2}}\right)^2=\\ =2x_0^2+y_0^2-8x_0-4y_0+12$$
to get the minimum we have to derivate that partially first on $x_0$ and then on $y_0$:
$$\dfrac{d}{dx_0} 2x_0^2+y_0^2-8x_0-4y_0+12 = 4x_0-8\\ \dfrac{d}{dy_0} 2x_0^2+y_0^2-8x_0-4y_0+12 = 2y_0-4$$
then put them equal to 0 (since we look for the minimum) and put everything into a system of equations:
$$ \left\{ \begin{array}{l} 4x_0-8=0\\ 2y_0-4=0 \end{array} \right. $$
from where we obtain $$p (2, 2)$$