Geometric tests

Line-line intersection

Given two lines in 3D defined as rays

r_{1} (t_{1}) = p_{1} + t_{1} d_{1} r_{2} (t_{2}) = p_{2} + t_{2} d_{2}

Where $t_{1}, t_{2} \in R$ , the two lines intersect if

p_{1} + t_{1} d_{1} = p_{2} + t_{2} d_{2}

We can apply the cross multiplication operation on both sides with $d_{2}$ and work from there to find the value of $t_{1}$

t_{1} = \frac{| (p_{2} - p_{1}) \times d_{2} |}{| d_{1} \times d_{2} |}

Similarly we can find the value of $t_{2}$ by crossing with $d_{1}$ and work from there to find the value of $t_{2}$

t_{2} = \frac{| (p_{2} - p_{1}) \times d_{1} |}{| d_{1} \times d_{2} |}

The proof can be found here

We can actually solve this problem graphically by using triangle similarity , imagine the following situation

The intersection point $p$ is equal to

\begin{matrix} (1) & \begin{aligned} p & = a + | p - a | \hat{b - a} \\ = a + | p - a | \frac{b - a}{| b - a |} \end{aligned} \end{matrix}

By triangle similarity we see that

\frac{| p - a |}{| b - a |} = \frac{| n - a |}{| m - a |}

Multiplying the left side with an identity

\begin{matrix} (2) & \frac{| p - a |}{| b - a |} = \frac{| n - a |}{| m - a |} \frac{| d - c |}{| d - c |} \end{matrix}

We see that the quantity $| n - a | | d - c |$ is equal to the equation of the area of a parallelogram, we can skew the parallelogram (in the graphic towards the $x$ -axis) so that the left side becomes $c - a$ and the bottom side $d - c$ (which is not affected by the skew), note that the area can also be expressed with the cross product of the vectors $c - a$ and $d - c$ therefore

\begin{matrix} (3) & | n - a | | d - c | = | (c - a) \times (d - c) | \end{matrix}

A similar equation can be derived for the parallelogram with sides $m - a$ and $d - c$ , only this time the skewed side will become $b - a$

\begin{matrix} (4) & | m - a | | d - c | = | (b - a) \times (d - c) | \end{matrix}

Replacing $(3)$ , $(4)$ in $(2)$ and $(1)$ we see that the intersection point is equal to

p = a + (b - a) \frac{| (c - a) \times (d - c) |}{| (b - a) \times (d - c) |}

References

Intersection between two segments. [online] Stackoverflow.com. Available at: http://stackoverflow.com/a/565282/3341726 [Accessed 10 Mar. 2016].

Palacios, R. (2012). Geometria Computacional. (presentation given at the UCB for the ICPC 2012)

Lee, J. (2008). Similar triangles [online] Math.washington.edu. Available at: https://www.math.washington.edu/~lee/Courses/444-5-2008/supplement3.pdf [Accessed 10 Mar. 2016].

Line-line intersection

References

See Also

Affine spaces

Projective space

Culling & Clipping