I’d not have to explain how common this problem is. You would have to solve it at any time when doing collision checking. So, I just want to explain a few lines on solving it in this short article.
1> Finding intersection of 2 lines that already have their formulas:
Assume you have to check whether two lines: d1 and d2 have intersection or not. The formulas for d1 and d2 are as following:
(d1) y1 = a1*x + b1
(d2) y2 = a2*x + b2
If d1 intersects d2 at the point I(xi, yi) so:
yi = a1*xi + b1 and also,
yi = a2*xi + b2. This means: a1*xi + b1 = a2*xi + b2
xi = (b2 - b1)/(a2 - a1), then replace value of x with xi in the formula to find yi.
2> Finding intersection of 2 line segments
Expanding a little, what if we have to find the intersection of two line segments?
A line segment is identified by two points as its two ends. For example, finding the intersection of AB and CD in which identified by A(xA, yA), B(xB, yB) and C(xC, yC), D(xD, yD) respectively.
First, we have to find the formulas that describes the lines contain AB and CD.
Algorithm of finding formula of the line going through 2 points, let say A and B:
(d) y = a*x + b
A, B in (d) so:
yA = a*xA + b
yB = a*xB + b
=> yA - yB = a*(xA - xB) => a = (yA-yB)/(xA-xB); then we can easily find b.
At this step, the problem is simply turned back into the first problem which is finding intersection of two lines that have identified formulas.
3> Checking the intersection is inside the line segment:
If the intersection is found at I(xI, yI) and is inside the line segment AB, then this following logical expression is TRUE:
(xA - xI)*(xB - xI) <= 0 OR (yA- yI)*(yB - yI) <= 0
Finally, I intended to write some code sample, however, I think you can do it easily or you can ask me for help whenever you need 🙂 … or I will write it here one day 🙂