It took me a suprisingly long time on a plane ride to figure a formula for the intersection point of two line segments

The general idea is to set up a system of parametric equations where `t`

ranges from 0 (output is the first endpoint of the segment) to 1 (output is the first endpoint of the segment)

`x`_{0} = x_{0:0} * (1 - t_{0}) + x_{0:1} * t_{0}

`y`_{0} = y_{0:0} * (1 - t_{0}) + y_{0:1} * t_{0}

`x`_{1} = x_{1:0} * (1 - t_{1}) + x_{1:1} * t_{1}

`y`_{1} = y_{1:0} * (1 - t_{1}) + y_{1:1} * t_{1}

Since we are solving for an intersection point, `x`

and _{0} = x_{1}`y`

.
Thus we end up with two equations each with two unknowns: _{0} = y_{1}`t`

and _{0}`t`

_{1}

`x`_{0:0} * (1 - t_{0}) + x_{0:1} * t_{0} = x_{1:0} * (1 - t_{1}) + x_{1:1} * t_{1}

`y`_{0:0} * (1 - t_{0}) + y_{0:1} * t_{0} = y_{1:0} * (1 - t_{1}) + y_{1:1} * t_{1}

With a bit of algebra it is straightforward to solve for both variables. If they both exist in the range `[0, 1]`

, the segments intersect. Find the intersection point by substituting their values into the original equations.