Code archives/Algorithms/Lines Intersect
This code has been declared by its author to be Public Domain code.
Download source code
| There's a few examples of this already, but I wanted to write my own so that I understand it.|
Note that it uses double precision throughout for accuracy, as otherwise the results on near-horizontal/vertical lines can be a touch erratic.
Speed tests: 5,000 iterations takes 1ms or less
Strict 'THE MATHS BIT Function intersect(x1:Double, y1:Double, x2:Double, y2:Double, u1:Double, v1:Double, u2:Double, v2:Double, xResult:Double var, yResult:Double var) Local m1:Double, m2:Double, b1:Double, b2:Double 'CALCULATE SLOPE OF EACH LINE AND CHECK FOR POTENTIAL DIVISION-BY-ZERO If (x2 - x1) <> 0 m1 = (y2 - y1) / (x2 - x1) Else m1 = (y2 - y1) EndIf If (u2 - u1) <> 0 m2 = (v2 - v1) / (u2 - u1) Else m2 = (v2 - v1) EndIf b1 = y1 - (m1 * x1) b2 = v1 - (m2 * u2) xresult = (v1 - y1 - (u1 * m2) + (x1 * m1)) / (m1 - m2) yResult = m1 * xResult + b1 'NOTES 'If m1 = m2 then both lines are parallel and will never intersect. 'If m1 = m2 AND b1 = b2, then both lines are colinear (i.e. the same). End Function 'END OF MATHS BIT 'DEMO CODE Graphics 800, 600 'define two lines as four pairs of x/y coordinates: 'line 1 Local x1:Double = 60, y1:Double = 450 Local x2:Double = 300, y2:Double = 50 'don't really need this as we'll use the mouse coords. 'line 2 Local u1:Double = 50, v1:Double = 100 Local u2:Double = 700, v2:Double = 525 'These vars will contain the intersection point. Local xC:Double, yC:Double While Not KeyDown(KEY_ESCAPE) intersect(x1, y1, Double(MouseX()), Double(MouseY()), u1, v1, u2, v2, xC, yC) 'calculate the point of intersection (xC and yC) Cls Draw(x1, y1, MouseX(), MouseY(), u1, v1, u2, v2) 'Draw the lines SetColor 0, 0, 255 DrawOval xC - 5, yC - 5, 10, 10 'Draw oval at intersection point Flip Wend Function Draw(x1:Double, y1:Double, x2:Double, y2:Double, u1:Double, v1:Double, u2:Double, v2:Double) SetColor 255, 255, 0 DrawLine x1, y1, x2, y2 SetColor 255, 0, 0 DrawLine u1, v1, u2, v2 End Function 'END OF DEMO CODE
| Nice job. I just made a line intersection function for the same reason you did, and it turned out near-identical; great minds think alike. ;)|
Also, you can check for intersection between line segments as opposed to lines as well by checking if the intersection point is between the endpoints of both lines by adding this to the end of your function
If Between(X, X1, X2) And Between(Y, Y1, Y2) And Between(X, X3, X4) And Between(Y, Y3, Y4) 'Line segments intersect, return 1 Return 1 EndIf Return 0
Here's the Between function:
Function Between:Int(X:Float, B:Float, T:Float) If T > B If X > B And X < T Return 1 EndIf Else If X > T And X < B Return 1 EndIf EndIf Return 0 EndFunction
Might slow it down a bit, which is why I made a separate function to check for segment intersection.
| Thanks for that. I was going to add that later but you just saved me the trouble. ;) |
| Thanks both.|
Small error in the code above (that goes unnoticed if you don't need to check for colinear lines )
b2 = v1 - (m2 * u2)
b2 = v1 - (m2 * u1)
Code Archives Forum