Geometric Toolkit I

Problem: Compute the distance $d$ from a point $q$ to a line $p + t \; v$.

We assume that $|v| = 1$. If not, normalize $v$ first.

Then $(q-p) \cdot v$ is the length of the perpendicular projection of $(q-p)$ onto the line of $v$ (recall the dot product in the vector review notes) and $((q-p) \cdot v)\ v$ is the vector that is the perpendicular projection of $(q-p)$ onto the line of $v$.

Subtracting that projection vector from $(q-p)$ gives the perpendicular vector, from which we can take the length:

$d = | (q-p) - ((q-p) \cdot v) v |$

Problem: Find whether the perpendicular projection of a point, $p$, onto the line of a segment, $ab$, is between the segment endpoints or is beyond one of the endpoints.

In the diagram below, the projection of $p$ is beyond the endpoint $b$.

The $ab$ segment can be parameterized as $$s(t) = a + t\ (b-a)$$

Then $s(0) = a$ and $s(1) = b$. If $t < 0$, then $s(t)$ is beyond $a$. If $t > 1$, then $s(t)$ is beyond $b$. Otherwise, $s(t)$ is inside the segment.

The point that is the projection of $p$ onto the line of segment $ab$ has $$t = { (p-a) \cdot (b-a) \over (b-a) \cdot (b-a) }$$

from which we can determine whether $p$ projects between the endpoint, or beyond one of the endpoints.

The following operation is used in "point-n-perspective" methods, which we'll discuss in a later lecture.

Problem: Compute the points at which two lines, $\ell_1(t_1) = p_1 + t_1 v_1$ and $\ell_2(t_2) = p_2 + t_2 v_2$, approach most closely.

Again, we'll assume that $|v_1| = |v_2| = 1$.

At the closest approach, the vector from one line to the other is perpendicular to each line:

$\begin{eqnarray} ( \ell_1(t_1) - \ell_2(t_2) ) \cdot v_1 & = & 0 \\ ( \ell_1(t_1) - \ell_2(t_2) ) \cdot v_2 & = & 0 \\ \end{eqnarray}$

Expanding the first equation above:

$\begin{eqnarray} ( p_1 + t_1 v_1 - p_2 - t_2 v_2 ) \cdot v_1 & = & 0 \\ p_1 \cdot v_1 + t_1 v_1 \cdot v_1 - p_2 \cdot v_1 - t_2 v_2 \cdot v_1 & = & 0 \\ (p_1 \cdot v_1 - p_2 \cdot v_1) + (v_1 \cdot v_1) t_1 - (v_2 \cdot v_1) t_2 & = & 0 \\ \end{eqnarray}$

Similarly, the second equation is of the same form:

$(p_1 \cdot v_2 - p_2 \cdot v_2) + (v_1 \cdot v_2) t_1 - (v_2 \cdot v_2) t_2 = 0$

The two equations can be written as a matrix equation:

$\left[ \begin{array}{cc} (v_1 \cdot v_1) & -(v_2 \cdot v_1) \\ (v_1 \cdot v_2) & -(v_2 \cdot v_2) \\ \end{array} \right] \; \left[ \begin{array}{c} t_1 \\ t_2 \end{array} \right] = \left[ \begin{array}{c} p_2 \cdot v_1 - p_1 \cdot v_1 \\ p_2 \cdot v_2 - p_1 \cdot v_2 \\ \end{array} \right]$

And can be solved for $t_1$ and $t_2$, given the points $\ell_1(t_1)$ and $\ell_2(t_2)$ at the closet approach.