# Find the line closest (SSD) to 2 2D points passing through a 3rd point

Given 3 homogeneous 2D points, $p=[p_x,p_y,1]$, $q=[q_x,q_y,1]$, and $v=[v_x,v_y,v_z]$, with $p$ and $q$ finite (last coordinate is $1$), but $v_z$ maybe either $1$ - finite or $0$ - at infinity:

Find two new 2D points $p'$, $q'$ s.t. $d(p,p')^2+d(q,q')^2$ is minimized, with $d(p,q)$ the Euclidian distance) and $<l\equiv p' \times q', v> = 0$.

In words, find the line $l=[l_1,l_2,l_3]$ passing through $v$, that minimizes the sum of the squared Euclidean distances of $p$ and $q$ from $l$.

How can I find $l$? Even if only for the finite case where $v_z=1$.

(I previously asked a similar question, but here I'd like to minimize the sum of squared distances).

-

# Solution 1

Write the line we are looking for as: $ax+by+cz = 0$ (in the projective plane). The purpose is to determine the vectors of coefficients $(a,b,c)$. Since the line can be seen as a point in the dual plane, we shall consider the following normalization: $a^2+b^2+c^2 = 1$.

Then you can formulate the problem as follows: Minimize $d(l,p)^2 + d(l,q)^2$ under the constraints: $av_x + bv_y + cv_z = 0$ and $a^2+b^2+c^2 = 1$.

Now: $d(l,p)^2 = (ap_x +bp_y + c)^2/(a^2 + b^2)$ and $d(l,q)^2 = (aq_x +bq_y + c)^2/(a^2 + b^2)$

Form the lagrangian of optimization problem: $$L(a,b,c,u,v) = \frac{(ap_x +bp_y + c)^2}{a^2 + b^2} + \frac{(ap_x +bp_y + c)^2}{a^2 + b^2} +u(av_x + bv_y + cv_z) + v(a^2+b^2+c^2-1)$$

You need to compute the derivative with respect to $a$, $b$, $c$, $u$, $v$, then multiply by denominator and you get a polynomial system to solve.

Note that the Lagrange multipliers $(u,v)$ are auxiliary unknowns. The second solution avoids introducing these unknowns.

# Solution 2:

Take 2 distinct lines $l_1$ and $l_2$ passing through $v$. Then the line we are looking for can be written $l=\alpha l_1 + \beta l_2$.

Express the function to be minimized as a function of $\alpha$ and $\beta$. Take the derivative and you will take a polynomial in $\alpha, \beta$ (it should be homogeneous).

-
Solution 2, seems simpler than solution 1 (though I haven't worked out the equations yet...). Two possible options for $l_1$ and $l_2$ are: (1) the 2 lines passing through $p$ and $q$ and (2) the vertical and horzintal lines passing through $v$. (1) should work regardless of $v$ being at infinity but (2) will add some $0$s to the equations and possibly make them simpler. Can you recommend which 2 line should make the equations more tractable? – Adi Shavit Dec 23 '12 at 7:51