One of the most common tasks done with lines is detecting their intersection. For some reason, not many people know how to do that on a computer. In this post, I assume you have some lines. You got them from some algorithm, or the user supplied them, or whatever. And you want to find the intersection of these lines.

Ideally, the lines should be in the form Ax + By = C. But usually, that is not the case. But it is simple enough to convert it into this form. This is done using the two point form of the line.

We can generate two points on the line using the given form, And then plug those points into the above equation. And thus you'll get the equation in the form we want.

Rearranging the two-point equation, we get: (just try and understand them... they're not as horrible as they seem :P)

On opening the brackets on the right hand, we get:

And multiplying by (x_{1}-x_{2}) and rearranging, we get:

Compare this to Ax + By = C... and you'll see that we have our equation!

- A = y
_{2}- y_{1} - B = x
_{1}- x_{2} - C = B
*y*x_{1}+ A_{1}

So, convert all your lines into this form, and we're ready for step 2. Actually figuring out intersection points.

Right now, we have several lines in the form Ax + By = C. So "solving for intersection" is just solving a set of equations:

A_{1}x + B_{1}y = C_{1} A_{2}x + B_{2}y = C_{2}

To solve, multiply the first equation with B_{2} and the second with B_{1}. Then you end up with:

A_{1}B_{2}x + B_{1}B_{2}y = B_{2}C_{1} A_{2}B_{1}x + B_{1}B_{2}y = B_{1}C_{2}

Subtract the second equation from the first and you get:

A_{1}B_{2}x - A_{2}B_{1}x = B_{2}C_{1 - }B_{1}C_{2}

And thus, we get the x coordinate of intersection:

x = (B_{2}C_{1 - }B_{1}C_{2}) / det

Where det = A_{1}B_{2} - A_{2}B_{1}

Similarly, you can derive an equation for y. And finally, we arrive at these results:

- x = (B
_{2}C_{1}- B_{1}C_{2}) / det - y = (A
_{1}C_{2}- A_{2}C_{1}) / det

If det = 0, then the lines are parallel (so you cannot calculate x and y)

Translate the equations in bullet lists into a program. And you have a program that solves for intersection of lines!