1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ but a line is given by $ax+by+c=0$ with real numbers $a,b,c$ $\endgroup$ – Dr. Sonnhard Graubner Dec 23 '15 at 13:06
  • $\begingroup$ @Dr.SonnhardGraubner If you wish to use that terminology then do this: $y = -\frac{a}{b} x - \frac{c}{b}$ Then you'll see how those combinations of your constants are equivalent to my constants in the equation $y = ax + b$ $\endgroup$ – Jonathan Mee Dec 23 '15 at 13:09
  • $\begingroup$ but you must do casework the variable $b$ can be zero this equation is better than yours $\endgroup$ – Dr. Sonnhard Graubner Dec 23 '15 at 13:11
  • $\begingroup$ @Dr.SonnhardGraubner If you like we can define your variables as: $a = y_0 - y_1$, $b = x_1 - x_0$, and $c = x_0 y_1 - y_0 x_1$ for the first line and $a = y_{10} - y_{11}$, $b = x_{11} - x_{10}$, and $c = x_{10} y_{11} - y_{10} x_{11}$ for the second line. Then we can plug them into the intersection equation and it'll simplify to the exact same thing. The intersection equations will find the points whether we use your line definitions or mine. $\endgroup$ – Jonathan Mee Dec 23 '15 at 13:17
  • $\begingroup$ @Dr.SonnhardGraubner It may be worth noting that the explicit form of the intersection equation may have been used to arrive at the algorithm's equations, as it has separated the components into terms that are more readily reflected explicitly. $\endgroup$ – Jonathan Mee Dec 23 '15 at 16:13
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.