Intersections of two lines

[Windsurfer]

Okay, a while back i had been messing with this line intersect function... It is supposed to return true if two lines are intersecting. For some reason, it gives false positives, but no false negatives. Any help by anyone? I can't get a concrete example of when it gives the false positive, as it relies on real numbers and happens infrequently... but it has quite an impact when checking multiple lines.

code:

function Pt_In_Rec (h, v, rec_x1, rec_y1, rec_x2, rec_y2 : real) : boolean     %more complex and thorugh than original     result (((h >= rec_x1) and (h <= rec_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and         (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2))) end Pt_In_Rec function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean     %This function returns true if the segments intersect     %if they don't, this **should** be able to find the point that the "lines" intersect     %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0     %uses form y = m*x + b     if x1 = x2 and y1 = y2 then % if the "line" is a point         if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then             point_x := x1             point_y := y1             result true         end if     end if     if h1 = h2 and v1 = v2 then     % if the "line" is a point         if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then             point_x := h1             point_y := v1             result true         end if     end if     % the "lines" aren't points, so find slopes and y-intercepts     var m1, m2, b1, b2 : real     if x2 not= x1 then     %if line 1 is not vertical, keep going         m1 := (y2 - y1) / (x2 - x1)         if h2 not= h1 then     %is line 2 vertical?             m2 := (v2 - v1) / (h2 - h1)             %everything is normal             %w00t         else     %line 2 is vertical! but line 1 is not!             b1 := y1 - m1 * x1             point_x := h1             point_y := b1 + m1 * point_x             if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and                     ((point_y < v1 and point_y > v2) or (point_y > v1 and point_y < v2)) then                 result true             else                 result false             end if         end if         b1 := y1 - m1 * x1         b2 := v1 - m2 * h1     else     %line 1 is vertical         if h2 not= h1 then     %if line 2 is not vertical, find slope and y-int             m2 := (v2 - v1) / (h2 - h1)             b2 := v1 - m2 * h1         else             %line 2 is vertical!             if h1 = x1 then     %if lines are overlapping, return true                 %lines overlap!                 point_x := x1                 point_y := (y1 + y2 + v1 + v2) / 4                 result true             else                 %lines are not overlapping!                 result false             end if         end if         %line 2 is not vertical here         point_x := x1         point_y := b2 + m2 * point_x         if Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) and                 ((point_y < y1 and point_y > y2) or (point_y > y1 and point_y < y2)) then             result true         else             result false         end if     end if     if m1 not= m2 then     %if parallel         point_x := - (b1 - b2) / (m1 - m2)     else         if x1 = h1 and x2 = h2 and y1 = v1 and y2 = v2 then             %find average point(yeah, not mathematic, but meh, it works for games)             point_x := (x1 + x2 + h1 + h2) / 4             point_y := (y1 + y2 + v1 + v2) / 4             result true         else             result false  %it's dead! can't intersect         end if     end if     point_y := b1 + m1 * point_x %find second point if all is good     if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) then         %is the point inside the lines?         result true %it is!     else         result false %it's not!     end if end Intersect_Seg

Hopefully it isn't too complicated.... I made it so that it uses y = mx + b format, with extra stuff to correct it when m = infinity and so on.

[BenLi]

well without reading your code, you said

Quote:

It is supposed to return true if two lines are intersecting

Any two lines will intersect if it's not parallel. Why don't you check that instead?

[Bored]

When he says lines he is talking about line segments. Therfore even though the extended line will touch it does not mean that the line segments are touching. So instead he needs to find the point of intersection and see if its within both line segments or atleast thats what I think he's doing.

[Bored]

I added this code to the bottom to generate random lines and test your program:

code:

View.Set ("nocursor") var x, y : array 1 .. 5 of real loop     for i : 1 .. 4         x (i) := Rand.Int (0, maxx - 1) + Rand.Real         y (i) := Rand.Int (0, maxy - 1) + Rand.Real     end for     drawline (round (x (1)), round (y (1)), round (x (2)), round (y (2)), red)     drawline (round (x (3)), round (y (3)), round (x (4)), round (y (4)), blue)     put Intersect_Seg (x (1), y (1), x (2), y (2), x (3), y (3), x (4), y (4), x (5), y (5))     drawfilloval (round (x (5)), round (y (5)), 2, 2, green)     exit when getchar = KEY_ESC     cls end loop

And after extensive trials I have not seen one wrong case. Try it for yourself. If you find one that is wrong take a picture and post it as it seems to work fine for me. Maybe your just implimenting it into another program wrong or something like that.

[Windsurfer]

Well, if you've ever played my game Forces you may have noticed what i call "offscreen bubbles". What i'm actually doing is finding the intersection of a line drawn from the center of the screen to where the enemy is. Where it intersects the border, i put a bubble. You may have noticed it flickering... But that's just one example.

But here is that same problem written as a program. Try moving your mouse around the outside, and watch the line flicker.

code:

%this algorythm was made by Adam Bilinski %very usefol for many games var mouse_x, mouse_y, button : int := 0 const X_SCREEN := 650 const Y_SCREEN := 600 setscreen ("graphics:" + intstr (X_SCREEN) + ";" + intstr (Y_SCREEN)) const C_X := X_SCREEN div 2 const C_Y := Y_SCREEN div 2 View.Set ("offscreenonly") function Pt_Near (h1, v1, h2, v2, dist : real) : boolean     %which method is faster?     %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1)) < dist     result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) < dist end Pt_Near function Pt_Dist (h1, v1, h2, v2 : real) : real     %which method is faster?     %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1) )     result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) end Pt_Dist function Pt_In_Rec (h, v, rec_x1, rec_y1, rec_x2, rec_y2 : real) : boolean     %more complex and thorugh than original     result (((h >= rec_x1) and (h <= rec_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and         (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2))) end Pt_In_Rec function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean     %This function returns true if the segments intersect     %if they don't, this **should** be able to find the point that the "lines" intersect     %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0     %uses form y = m*x + b     if x1 = x2 and y1 = y2 then % if the "line" is a point         if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then             point_x := x1             point_y := y1             result true         end if     end if     if h1 = h2 and v1 = v2 then     % if the "line" is a point         if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then             point_x := h1             point_y := v1             result true         end if     end if     % the "lines" aren't points, so find slopes and y-intercepts     var m1, m2, b1, b2 : real     if x2 not= x1 then     %if line 1 is not vertical, keep going         m1 := (y2 - y1) / (x2 - x1)         if h2 not= h1 then     %is line 2 vertical?             m2 := (v2 - v1) / (h2 - h1)             %everything is normal             %w00t         else     %line 2 is vertical! but line 1 is not!             b1 := y1 - m1 * x1             point_x := h1             point_y := b1 + m1 * point_x             if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and                     ((point_y < v1 and point_y > v2) or (point_y > v1 and point_y < v2)) then                 result true             else                 result false             end if         end if         b1 := y1 - m1 * x1         b2 := v1 - m2 * h1     else     %line 1 is vertical         if h2 not= h1 then     %if line 2 is not vertical, find slope and y-int             m2 := (v2 - v1) / (h2 - h1)             b2 := v1 - m2 * h1         else             %line 2 is vertical!             if h1 = x1 then     %if lines are overlapping, return true                 %lines overlap!                 point_x := x1                 point_y := (y1 + y2 + v1 + v2) / 4                 result true             else                 %lines are not overlapping!                 result false             end if         end if         %line 2 is not vertical here         point_x := x1         point_y := b2 + m2 * point_x         if Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) and                 ((point_y < y1 and point_y > y2) or (point_y > y1 and point_y < y2)) then             result true         else             result false         end if     end if     if m1 not= m2 then     %if parallel         point_x := - (b1 - b2) / (m1 - m2)     else         if x1 = h1 and x2 = h2 and y1 = v1 and y2 = v2 then             %find average point(yeah, not mathematic, but meh, it works for games)             point_x := (x1 + x2 + h1 + h2) / 4             point_y := (y1 + y2 + v1 + v2) / 4             result true         else             result false  %it's dead! can't intersect         end if     end if     point_y := b1 + m1 * point_x %find second point if all is good     if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) then         %is the point inside the lines?         result true %it is!     else         result false %it's not!     end if end Intersect_Seg function Out_Of_Bounds (h1, v1, x1, y1, x2, y2 : real, var point_x : real, var point_y : real) : boolean     if Pt_In_Rec (h1, v1, x1, y1, x2, y2) then         result false     else         const C_X := (x2 - x1) / 2         const C_Y := (y2 - y1) / 2         if Intersect_Seg (C_X, C_Y, h1, v1, x1, y1, x1, y2, point_x, point_y) then         elsif Intersect_Seg (C_X, C_Y, h1, v1, x1, y2, x2, y2, point_x, point_y) then         elsif Intersect_Seg (C_X, C_Y, h1, v1, x2, y2, x2, y1, point_x, point_y) then         elsif Intersect_Seg (C_X, C_Y, h1, v1, x2, y1, x1, y1, point_x, point_y) then         else             result false         end if         result true     end if end Out_Of_Bounds loop     Mouse.Where (mouse_x, mouse_y, button)     if not Pt_In_Rec (mouse_x, mouse_y, 0, 0, X_SCREEN, Y_SCREEN) then         var x1, y1 : real := 0         if Out_Of_Bounds (mouse_x, mouse_y, 20, 20, X_SCREEN - 20, Y_SCREEN - 20, x1, y1) then             var x2, y2 : real := 0             var dist : real := Pt_Dist (C_X, C_Y, mouse_x, mouse_y)             const size := dist / 5             x2 := (C_X - mouse_x) / dist * size             y2 := (C_Y - mouse_y) / dist * size             drawline (round (x1), round (y1), round (x1 + x2), round (y1 + y2), black)         end if     end if     View.Update     delay (10)     cls end loop

[zylum]

i dont see any flicker either. here's a simple function thats a little easier to read:

code:

fcn intercept (x1, y1, x2, y2, x3, y3, x4, y4 : int, var px, py : int) : boolean     var m1 := (y2 - y1) / (x2 - x1 + 1e-5)     var m2 := (y4 - y3) / (x4 - x3 + 1e-5)     var b1 := y1 - m1 * x1     var b2 := y3 - m2 * x3     var x := (b1 - b2) / (m2 - m1)     px := round (x)     py := round (m1 * x + b1)     result px >= min (x1, x2) & px <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4) end intercept

[Windsurfer]

Okay, your function does work, and IS easier to read, but it doesn't work for line segments. It also doesn't work if one of the lines is vertical... which is kind of critical. It also doesn't work if a line is a point, and it ALSO doesn't always return the right boolean. Take a look.... move your mouse off the right of the screen:

code:

var mouse_x, mouse_y, button : int := 0 const X_SCREEN := 650 const Y_SCREEN := 600 setscreen ("graphics:" + intstr (X_SCREEN) + ";" + intstr (Y_SCREEN)) const C_X := X_SCREEN div 2 const C_Y := Y_SCREEN div 2 View.Set ("offscreenonly") function Pt_Near (h1, v1, h2, v2, dist : real) : boolean     %which method is faster?     %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1)) < dist     result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) < dist end Pt_Near function Pt_Dist (h1, v1, h2, v2 : real) : real     %which method is faster?     %result sqrt ((h2 - h1) *(h2 - h1) + (v2 - v1) *(v2 - v1) )     result sqrt ((h2 - h1) ** 2 + (v2 - v1) ** 2) end Pt_Dist function Pt_In_Rec (h, v, rec_x1, rec_y1, rec_x2, rec_y2 : real) : boolean     %more complex and thorugh than original     result (((h >= rec_x1) and (h <= rec_x2)) or ((h <= rec_x1) and (h >= rec_x2))) and         (((v >= rec_y1) and (v <= rec_y2)) or ((v <= rec_y1) and (v >= rec_y2))) end Pt_In_Rec function Intersect_Seg (x1, y1, x2, y2, h1, v1, h2, v2 : real, var point_x : real, var point_y : real) : boolean     %This function returns true if the segments intersect     %if they don't, this **should** be able to find the point that the "lines" intersect     %if they don't intersect at all (eg. parallel lines not overlapping), then the point will be 0,0     %uses form y = m*x + b     if x1 = x2 and y1 = y2 then % if the "line" is a point         if ((x1 = h1) or (x1 = h2)) and ((y1 = v1) or (y1 = v2)) then             point_x := x1             point_y := y1             result true         end if     end if     if h1 = h2 and v1 = v2 then     % if the "line" is a point         if ((h1 = x1) or (h1 = x2)) and ((v1 = y1) or (v1 = y2)) then             point_x := h1             point_y := v1             result true         end if     end if     % the "lines" aren't points, so find slopes and y-intercepts     var m1, m2, b1, b2 : real     if x2 not= x1 then     %if line 1 is not vertical, keep going         m1 := (y2 - y1) / (x2 - x1)         if h2 not= h1 then     %is line 2 vertical?             m2 := (v2 - v1) / (h2 - h1)             %everything is normal             %w00t         else     %line 2 is vertical! but line 1 is not!             b1 := y1 - m1 * x1             point_x := h1             point_y := b1 + m1 * point_x             if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and                     ((point_y < v1 and point_y > v2) or (point_y > v1 and point_y < v2)) then                 result true             else                 result false             end if         end if         b1 := y1 - m1 * x1         b2 := v1 - m2 * h1     else     %line 1 is vertical         if h2 not= h1 then     %if line 2 is not vertical, find slope and y-int             m2 := (v2 - v1) / (h2 - h1)             b2 := v1 - m2 * h1         else             %line 2 is vertical!             if h1 = x1 then     %if lines are overlapping, return true                 %lines overlap!                 point_x := x1                 point_y := (y1 + y2 + v1 + v2) / 4                 result true             else                 %lines are not overlapping!                 result false             end if         end if         %line 2 is not vertical here         point_x := x1         point_y := b2 + m2 * point_x         if Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) and                 ((point_y < y1 and point_y > y2) or (point_y > y1 and point_y < y2)) then             result true         else             result false         end if     end if     if m1 not= m2 then     %if parallel         point_x := - (b1 - b2) / (m1 - m2)     else         if x1 = h1 and x2 = h2 and y1 = v1 and y2 = v2 then             %find average point(yeah, not mathematic, but meh, it works for games)             point_x := (x1 + x2 + h1 + h2) / 4             point_y := (y1 + y2 + v1 + v2) / 4             result true         else             result false  %it's dead! can't intersect         end if     end if     point_y := b1 + m1 * point_x %find second point if all is good     if Pt_In_Rec (point_x, point_y, x1, y1, x2, y2) and Pt_In_Rec (point_x, point_y, h1, v1, h2, v2) then         %is the point inside the lines?         result true %it is!     else         result false %it's not!     end if end Intersect_Seg fcn intercept (x1, y1, x2, y2, x3, y3, x4, y4 : real, var px, py : real) : boolean     var m1 := (y2 - y1) / (x2 - x1 + 1e-5)     var m2 := (y4 - y3) / (x4 - x3 + 1e-5)     var b1 := y1 - m1 * x1     var b2 := y3 - m2 * x3     var x := (b1 - b2) / (m2 - m1)     px := x     py := m1 * x + b1     result px >= min (x1, x2) & px <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4) end intercept function Out_Of_Bounds (h1, v1, x1, y1, x2, y2 : real, var point_x : real, var point_y : real) : boolean     if Pt_In_Rec (h1, v1, x1, y1, x2, y2) then         result false     else         const C_X := (x2 - x1) / 2         const C_Y := (y2 - y1) / 2         if intercept (C_X, C_Y, h1, v1, x1, y1, x1, y2, point_x, point_y) then         elsif intercept (C_X, C_Y, h1, v1, x1, y2, x2, y2, point_x, point_y) then         elsif intercept (C_X, C_Y, h1, v1, x2, y2, x2, y1, point_x, point_y) then         elsif intercept (C_X, C_Y, h1, v1, x2, y1, x1, y1, point_x, point_y) then         else             result false         end if         result true     end if end Out_Of_Bounds loop     Mouse.Where (mouse_x, mouse_y, button)     if not Pt_In_Rec (mouse_x, mouse_y, 0, 0, X_SCREEN, Y_SCREEN) then         var x1, y1 : real := 0         put "Mouse is outside of window"         if Out_Of_Bounds (mouse_x, mouse_y, 20, 20, X_SCREEN - 20, Y_SCREEN - 20, x1, y1) then             var x2, y2 : real := 0             var dist : real := Pt_Dist (C_X, C_Y, mouse_x, mouse_y)             const size := dist / 5             x2 := (C_X - mouse_x) / dist * size             y2 := (C_Y - mouse_y) / dist * size             drawline (round (x1), round (y1), round (x1 + x2), round (y1 + y2), black)         else             put "But line was not drawn."         end if     end if     View.Update     delay (10)     cls end loop

[zylum]

k, this one should work a little better:

code:

fcn intercept (x1, y1, x2, y2, x3, y3, x4, y4 : real, var px, py : real) : boolean     var m1 := (y2 - y1) / (x2 - x1 + 1e-3)     var m2 := (y4 - y3) / (x4 - x3 + 1e-3)     var b1 := y1 - m1 * x1     var b2 := y3 - m2 * x3     var x := (b1 - b2) / (m2 - m1 + 1e-4)     px := round (x)     py := round (m1 * x + b1)     result px >= min (x1, x2) & px <= max (x1, x2) & px >= min (x3, x4) & px <= max (x3, x4) &         py >= min (y1, y2) & py <= max (y1, y2) & py >= min (y3, y4) & py <= max (y3, y4) end intercept

[Windsurfer]

Wow. This works perfectly. Thanks... all I know is that your function works, and does resemble mine... sort of.
Anyhoo, this is awsome. Maybe now i can start putting walls in Forces.
+ bits