For the lines:
- $y = ax + b$
- $y = cx + d$
The standard intersection equation
- $x_i = \frac{d - b}{a - c}$
- $y_i = \frac{ad - bc}{a - c}$
If the points that I was given to find the line $y = ax + b$ were $(x_0, y_0)$ and $(x_1, y_1)$ and the points for the line $y = cx + d$ were $(x_{10}, y_{10})$ and $(x_{11}, y_{11})$ then I know the values for the line equations:
- $a = \frac{y_0 - y_1}{x_0 - x_1}$
- $b = \frac{x_0y_1 - y_0x_1}{x_0 - x_1}$
- $c = \frac{y_{10} - y_{11}}{x_{10} - x_{11}}$
- $d = \frac{x_{10}y_{11} - y_{10}x_{11}}{x_{10} - x_{11}}$
So substituting these into the intersection equations I get:
- $x_i = \cfrac{\frac{x_{10}y_{11} - y_{10}x_{11}}{x_{10} - x_{11}} - \frac{x_0y_1 - y_0x_1}{x_0 - x_1}}{\frac{y_0 - y_1}{x_0 - x_1} - \frac{y_{10} - y_{11}}{x_{10} - x_{11}}}$
- $y_i = \cfrac{\frac{y_0 - y_1}{x_0 - x_1}\frac{x_{10}y_{11} - y_{10}x_{11}}{x_{10} - x_{11}} - \frac{x_0y_1 - y_0x_1}{x_0 - x_1}\frac{y_{10} - y_{11}}{x_{10} - x_{11}}}{\frac{y_0 - y_1}{x_0 - x_1} - \frac{y_{10} - y_{11}}{x_{10} - x_{11}}}$
Moving the subtractions into a single fraction allows us to remove the nested denominators:
- $x_i = \frac{(x_0 - x_1)(x_{10}y_{11} - y_{10}x_{11}) - (x_0y_1 - y_0x_1)(x_{10} - x_{11})}{(y_0 - y_1)(x_{10} - x_{11}) - (x_0 - x_1)(y_{10} - y_{11})}$
- $y_i = \frac{(y_0 - y_1)(x_{10}y_{11} - y_{10}x_{11}) - (x_0y_1 - y_0x_1)(y_{10} - y_{11})}{(y_0 - y_1)(x_{10} - x_{11}) - (x_0 - x_1)(y_{10} - y_{11})}$
Now I have a C++ algorithm for solving line intersection which looks like this:
- $x_i = \frac{x_{11} \left| y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{10} + (x_0 - x_1) y_{10} \right| + x_{10} \left|y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{11} + (x_0 - x_1) y_{11} \right|}{\left|y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{10} + (x_0 - x_1) y_{10} \right| + \left| y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{11} + (x_0 - x_1) y_{11} \right|}$
- $y_i = \frac{y_{11} \left| y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{10} + (x_0 - x_1) y_{10} \right| + y_{10} \left|y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{11} + (x_0 - x_1) y_{11} \right|}{\left|y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{10} + (x_0 - x_1) y_{10} \right| + \left| y_0 x_1 - x_0 y_1 - (y_0 - y_1) x_{11} + (x_0 - x_1) y_{11} \right|}$
This algorithm won't work for non-intersecting lines, but if there is an intersection I haven't been able to find an example where it doesn't work. I've been trying to relate it to the original equation to find out how this algorithm was reached but I've had no luck. I've tried looking for perfect squares and trying to get the algorithm back into a form consisting of $a$, $b$, $c$, and $d$, but so far I haven't been able to.
Is there another line intersection equation this is a modification of? Or is there some other way I can factor this to prove what it's doing actually works?
You can derive the standard intersection formula and the one you got fairly easily using homogeneous coordinates. Both points and lines can be represented by triples. The line through two points can by found by taking their cross product, and the point at which two lines intersect is also given by their cross product (another happy instance of duality in the projective plane). This works even if the lines are parallel—you get the point at infinity, i.e., the third coordinate of the cross product is $0$.
As far as the more complicated expression that you have from C++ code goes, it reminds me of a formula for finding the intersection of two line segments, an explanation of which you can find here. If you ignore the constraints on $s_I$ and $t_I$, this procedure works for two lines as well. Note in particular that if you take the $Q(t_I)$ solution, using your notation the numerators look like $x_{11}(\dots)+x_{10}(\dots)$ and $y_{11}(\dots)+y_{10}(\dots)$. The resulting expressions for $x_i$ and $y_i$ aren’t exactly like the ones you have, though. The absolute values are puzzling as are the extra terms inside of them. However, they’re similar enough that I suspect a similar derivation of the formula you have.