Common algorithem: Line segment to line segment.

[Pixel_Outlaw]

I've done some searching before posting and I can't find much describing how to tell if line a intersects line b. Also if need be find the intersection between the two lines. I have heard that this is a common problem but I just havn't gotten much on the interweb.

[zawran]

I found this one in the blitzmax code section which might be of use:

Code Select Expand


Function LinesCross( x0:Float, y0:Float , x1:Float, y1:Float,..
x2:Float ,y2:Float, x3:Float, y3:Float )
 
Local n:Float=(y0-y2)*(x3-x2)-(x0-x2)*(y3-y2)
Local d:Float=(x1-x0)*(y3-y2)-(y1-y0)*(x3-x2)

If Abs(d) < 0.0001
' Lines are parallel!
Return False
Else
' Lines might cross!
Local Sn:Float=(y0-y2)*(x1-x0)-(x0-x2)*(y1-y0)

Local AB:Float=n/d
If AB>0.0 And AB<1.0
Local CD:Float=Sn/d
If CD>0.0 And CD<1.0
' Intersection Point
Local X=x0+AB*(x1-x0)
        Local Y=y0+AB*(y1-y0)
Return True
End If
End If

' Lines didn't cross, because the intersection was beyond the end points of the lines
EndIf

' Lines do Not cross!
Return False

End Function


[rain_storm]

Heres another meathod that I came across dont remember where exactly but its quite ingenious

Code Select Expand


sub segment2segment(x0,y0,x1,y1, x2,y2,x3,y3)
  local denom, nume_a, nume_b
  denom  = ((y3 - y2)*(x1 - x0)) - ((x3 - x2)*(y1 - y0))
  nume_a = ((x3 - x2)*(y0 - y2)) - ((y3 - y2)*(x0 - x2))
  nume_b = ((x1 - x0)*(y0 - y2)) - ((y1 - y0)*(x0 - x2))
  if (denom = 0.0) then // escape to avoid divide by zero
    if (nume_a = 0.0) and (nume_b = 0.0) return 0 // paralell
    return 0 // co-incident
  endif
  local ua, ub
  ua = nume_a / denom
  ub = nume_b / denom
  if (ua >= 0.0) and (ua <= 1.0) and (ub >= 0.0) and (ub <= 1.0) then
    xi = x0 + ua*(x1 - x0)
    yi = y0 + ua*(y1 - y0)
    return 1 // intersecting
  endif
  return 0 // not intersecting
end sub


Edit:
I think it may be the same as above sorry if it is

[Jim]

Here's some hints, if you can't find really good code on google (you should be able to find really good code on google).
- see if the two infinite lines that contain your two line segments cross.
- as you can imagine, if these two lines are nearly parallel that intersection might be a million miles away, and that will give you mathematical problems.
- you can easily find the distance of a point from a line.

Mind you, I've had code for quaternions and for rgb->yuv conversion off the net, from eclectic sources, and they've been wrong, wrong wrong.
If you're still stuck after looking, post again and I'll look in to it for you.

Jim

[frea]

Cormen's "bible" describes it afair.

[stormbringer]

have a look here: http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/

other nice algorithms too

[taj]

I've done some searching before posting and I can't find much describing how to tell if line a intersects line b. Also if need be find the intersection between the two lines. I have heard that this is a common problem but I just havn't gotten much on the interweb.

Get rid of your interweb. Its not working as it should. Probably it has been filled with too many blogs, e-spaces and me-tubes. Creaking under this weight, your internet has stopped working as it should. I upgraded my internet to version 1.00023.9a14-01-67 and I haven't had any problems. Once you upgrade try typing:

"algorithm two lines intersect"  into google. The first result has maths and code.

The only problem with my version (1.00023.9a14-01-67) is that I reached the end  http://www.romlist.com/end/
I tried a few other versions but they are just full of pr0n.