I need to find a distance between a point of intersection of two 2D segments ( that are defined by two points each) and a beginning of the first segment. The segments are guaranteed to intersect.
Here's an illustration:
I stumbled upon an algorithm to find such distance, which seems to give correct results. It consists of 3 steps:
1) $\vec{S2_{perp}} =[S2end.y - S2begin.y, S2begin.x - S2end.x]$
2) $S1_{proj} = \vec{(S1end - S1begin)} \cdot \vec{S2_{perp}}$
3) $Distance = \frac{(\vec{S2_{begin} - S1_{begin}}) \cdot \vec{S2_{perp}}}{ S1_{proj}} \cdot | S1_{end} - S1_{begin} |$
Unfortunately, no explanation of this method was given, and I don't quite understand how it works. I understand all the individual operations, i.e. getting vector perpendicular to segment two in first step, taking dot product with this vector and vector representing S1 in 2'nd step etc. But what I can't understand is why this particular set of operations gives correct result.
Can anyone explain this? Is there any geometrical intuition behind this algorithm?
This is a fairly straightforward application of similar triangles. Let $\mathscr l$ be the perpendicular line to $\overline{S_{2b}S_{2e}}$ through $S_{1b}$, $I$ the intersection point, and $P$ and $Q$ the feet of the altitudes to $\mathscr l$ from $I$ and $S_{1e}$, respectively. Then $\triangle{S_{1b}PI}\sim\triangle{S_{1b}QS_{1e}}$ and so $S_{1b}I = {S_{1b}P\over S_{1b}Q} S_{1b}S_{1e}$.
$\overline{S_{1b}Q}$ is of course the projection of $\overline{S_{1b}S_{1e}}$ onto $\mathscr l$ and $\overline{S_{1b}P}$ is the projection of $\overline{S_{1b}I}$, but the clever observation that is the key to this algorithm is that $\overline{S_{1b}P}$ is also the projection of $\overline{S_{1b}S_{2b}}$ onto $\mathscr l$. Let ${\vec S}_{2\perp}$ be $S_{2e}-S_{2b}$ rotated 90° (in either direction), i.e., a direction vector of $\mathscr l$. Applying the usual formula for orthogonal projection, we therefore have $$S_{1b}P = {| (S_{1e}-S_{1b})\cdot{\vec S}_{2\perp} | \over \|{\vec S}_{2\perp}\|}$$ and $$S_{1b}Q = {| (S_{2b}-S_{1b})\cdot {\vec S}_{2\perp} | \over \|{\vec S}_{2\perp}\|}.$$ The factors of $\|{\vec S}_{2\perp}\|$ in the denominators cancel when we compute the ratio of these two lengths, so we can omit them, and the absolute value signs can be dropped since the two dot products will have the same sign.
A somewhat more opaque algebraic derivation that leads to the same expression when expanded in terms of coordinates is as follows: Parameterize $\overline{S_{1b}S_{1e}}$ by the affine combination $(1-\lambda)S_{1b}+\lambda S_{1e}$. If $I=(1-\lambda_I)S_{1b}+\lambda_I S_{1e}$, then $S_{1b}I = \lambda_I \|S_{1e}-S_{1b}\|$. The value of $\lambda_I$ can be found by using the fact that $I$, $S_{2b}$ and $S_{2e}$ are colinear, which can be expressed by the equation $$\det \begin{bmatrix} (1-\lambda_I)x_{1b} + \lambda_I x_{1e} & x_{2b} & x_{2e} \\ (1-\lambda_I)y_{1b} + \lambda_I y_{1e} & y_{2b} & y_{2e} \\ 1&1&1 \end{bmatrix} = 0.$$ This is an easily-solved linear equation in $\lambda_I$.