Mathematics behind intersection points of two lines using quadratic equation

Question

This is the question I am trying to solve. I do not need any code examples just help on mathematics.

Suppose two line segments intersect. The two endpoints for the first line segment are $(x_1, y_1)$ and $(x_2, y_2)$ and for the second line segment are $(x_3, y_3)$ and $(x_4, y_4)$. Write a program that prompts the user to enter these four endpoints and displays the intersecting point. (Hint: Use the LinearEquation class from the preceding exercise.)

For the program to work I have to convert the endpoints of the lines into $a$, $b$, $c$, $d$, $e$, and $f$ so I can use the quadratic equation: $$x = \frac{(ed - bf)}{(ad - bc)} \\ \text{ } \\ y = \frac{(af - ec)}{(ad - bc)}$$

I cannot for the life of me through use of Google and such figure out how to convert the endpoints of each line into the variables I need for that equation. I have the class LinearEquation to use I just need to figure out how to solve for the variables in it. Any help would be greatly appreciated. This is not homework by the way, I have been self teaching myself Java so I don't have many resources. Thanks ahead of time!

P.S. I do not need any code examples. I am just really looking for someone to point me in the right direction on the mathematics behind how to do this. I have been looking for too long with no real answer.

Answer 1

You can use the two-point equation for a line to determine the equations for two lines.

$$ y = y_1 + \frac{y_2-y_1}{x_2-x_1}(x-x_1) $$

and

$$ y = y_3 + \frac{y_4-y_3}{x_4-x_3}(x-x_3)$$

Rearrange these to give $ax+by=c_1$ and $cx+dy=c_2$ and solve these by some usual technique for solving two-equations and two unknowns. I assume you have software for this.

You'll have to isolate special cases for this to work. If either of the line segments are vertical then the formulas break down. Also, if some sarcastic prof. puts the same pair of points in then you might want to account for the case of infinitely many points of intersection. Good luck.

Answer 2

Since you have two points for each line, we can find the formula for the unique line (assuming the points are distinct). For the first line, defined by $(x_1,y_1)$ and $(x_2,y_2)$, the slope is "rise-over-run", i.e. $\frac {y_2 - y_1} {x_2 - x_1}$, thus any point $x$ and $y$ on this line must have the same slope, so $$\frac {y - y_1} {x - x_1}= \frac {y_2 - y_1} {x_2 - x_1}\implies y=\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1\,.$$For the second line, we get the analogous result:

$$y=\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,.$$

Now we just have to solve these two equations, since we are looking for the point of intersection where the $x$ and $y$ variables for each line are equivalent, we set the $y's$ equal to each other and arrive at the equation:

$$\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1=\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,,$$ which we can simplify to $$\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]x= \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\,.$$

Now if $\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]\ne 0$ we can divide to find a specific formula for $x$: $$x=\frac 1 {\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)}\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\right]\,.$$ Now, finding $y$ will be easy - we just "back substitute" $x$ into either equation for $y$, say the first one:

$$y=\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)\left (\frac 1 {\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)}\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1-y_1 - \left ( \frac {y_4 - y_3} {x_4 - x_3}\right)x_3+y_3\right] \right) - \left ( \frac {y_2 - y_1} {x_2 - x_1}\right)x_1+y_1\,.$$

This will always work, unless we have that $\left[\left ( \frac {y_2 - y_1} {x_2 - x_1}\right)-\left ( \frac {y_4 - y_3} {x_4 - x_3}\right)\right]=0$. In that case, you either have coincident lines or parallel lines - to determine which, just check the y-intercept of each line (we already know the slopes are equal because of the above condition). If the y-intercepts of each line are equal to each other, then the lines are coincident (so there are infinitely many "points of intersection"). If not, they are parallel (and there are no points of intersection).