Intersection notes

Q: find closed-form formula for the intersection of two line segments in $$\bb{R}^2$$ given by $$(a,b)$$ and $$(c,d)$$.

First, just find the intersection of the two lines. The methodical approach: write them both as parametric equations, solve the system.

$p = a + (b-a) t \\ p = c + (d-c) s$

Set equal to each other and rearrange:

$(b-a) t - (d-c) s = c - a$

This is a set of $$n$$ equations for $$2$$ unknowns, so in general it’s overdetermined and may not have a solution. This makes sense: it reflects the fact that two line segments in $$\bb{R}^{n \geq 3}$$ may not intersect. The requirement that it has a solution is that $$(ab)$$ and $$(cd)$$ lay in the same plane. I believe (haven’t checked carefully) that this is equivalent to saying that $$(1,a) \^ (1,b) \^ (1,c) \^ (1,d) = 0$$, that is, their two lines have zero ‘volume’ (in projective $$n+1$$ space). This expands to $$(abcd) = 0$$ and $$(abc) - (abd) + (acd) - (bcd) = 0$$. There might be a cleaner way though. Seems to work from trying one trivial example.) Also, trivially, $$(b-a) \^ (d-c) \neq 0$$ is required, since the two lines have to be not collinear.

todo: come up with a clean, compact formula for these requirements?


Assuming that there is a solution, we can solve this equation in many ways, since any two coordinates that aren’t trivial should give us a valid system of equations for $$(t,s)$$. One mindless approach is to contract with the two coefficients in turn to create two scalar equations:

$(b-a) \cdot ((b-a) t - (d-c) s) = (b-a) \cdot (c-a) \\ (d-c) \cdot ((b-a) t - (d-c) s) = (d-c) \cdot (c-a)$

Or we can do it by eliminating variables Cramer’s rule, which is really just wedging by each vector in turn to cancel out the other ones. This gives:

\begin{aligned} [(d-c) \^ (b-a)] s &= (b-a) \^ (c-a) \\ [(d-c) \^ (b-a)] t &= (d - c) \^ (c-a) \end{aligned}

Both of these are equalities of bi-vectors, but if $$(b-a) \^ (d-c) \neq 0$$ then all three are parallel, so we can divide through by magnitudes, or just divide through on any single non-zero component since they all have to be the same.

todo: it would be nice to have a 'closed form' for $$t,s$$ here instead of this 'algorithm'.


$$p$$ is actually inside $$(a,b)$$ and $$(c,d)$$ if both $$s, t \in (0, 1)$$.