Line Intersection Algo.

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
Oz
Posts: 586
Joined: Jul 02, 2005 14:21
Location: Waterloo, Ontario, Canada
Contact:

Line Intersection Algo.

Post by Oz »

I got this from GameDev and recoded some of it. the original code can be found here

Anyway, this is it:

Code: Select all

Type Point2d
  x as single
  y as single
End Type

Type Line2d
  p1 as Point2d
  p2 as Point2d
End Type

Sub Line_Intersection( byval a as Line2d, byval b as Line2d, byref intersect as Point2d )
  dim as single x1, y1, z1, x2, y2, z2, det_inv, m1, m2

  if ( a.p1.x - a.p2.x ) <> 0 then
    m1 = ( a.p2.y - a.p1.y ) / ( a.p2.x - a.p1.x )
  else
    m1 = Exp( 1 ) + 10
  end if

  if ( b.p1.x - b.p2.x ) <> 0 then
    m2 = ( b.p2.y - b.p1.y ) / ( b.p2.x - b.p1.x )
  else
    m2 = Exp( 1 ) + 10
  end if

  x1 = m1
  x2 = m2

  y1 = -1
  y2 = -1

  z1 = ( a.p1.y-m1*a.p1.x )
  z2 = ( b.p1.y-m2*b.p1.x )

  det_inv = 1/(x1*y2 - x2*y1)

  intersect.x = ((y1*z2 - y2*z1)*det_inv)
  intersect.y = ((x2*z1 - x1*z2)*det_inv)

End Sub
does anyone have any optimizations? I'm working on a 2d game that does alot of line intersection for collision detection.

Any improvements are welcome (even changing the UDTs or whatever...as long as it is more efficient or speed)

thanks,
Oz
Last edited by Oz on Aug 12, 2007 18:00, edited 2 times in total.
Merick
Posts: 1038
Joined: May 28, 2007 1:52

Post by Merick »

m1 = 1/0????

will that really compile?
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Post by D.J.Peters »

Code: Select all

type point2d
  as integer x,y
end type
type line2d
  as point2d s,e ' start-end
end type

function LineLineIntersection(byval a   as line2d, _
                              byval b   as line2d, _
                              byref hit as point2d) as integer
   
  if a.s.x=a.e.x then a.e.x=a.s.x+1
  if b.s.x=b.e.x then b.e.x=b.s.x+1
  dim as single  m1=(a.e.y-a.s.y)/(a.e.x-a.s.x)
  dim as single  b1=a.s.y-a.s.x*m1
  dim as single  m2=(b.e.y-b.s.y)/(b.e.x-b.s.x)
  dim as single  b2=b.s.y-b.s.x*m2
  hit.x=(b2-b1)/(m1-m2)
  hit.y=m1*hit.x+b1
   
  if a.s.x > a.e.x then swap a.s.x,a.e.x
  if a.s.y > a.e.y then swap a.s.y,a.e.y
  if b.s.x > b.e.x then swap b.s.x,b.e.x
  if b.s.y > b.e.y then swap b.s.y,b.e.y
   
  if hit.x >= a.s.x then
    if hit.x <= a.e.x then
      if hit.x >= b.s.x then
        if hit.x <= b.e.x then
          if hit.y >= a.s.y then
            if hit.y <= a.e.y then
              if hit.y >= b.s.y then
                if hit.y <= b.e.y then
                  return -1
                endif
              endif
            endif
          endif
        endif
      endif
    endif
  endif
end function

' main
dim as line2d  a,b
dim as point2d hit
dim as integer c
a.s.x=480:a.s.y=120
a.e.x=160:a.e.y=360
screenres 640,480

while inkey=""
  if getmouse(b.e.x,b.e.y)=0 then
    screenlock:cls
    if LineLineIntersection(a,b,hit) then c=1 else c=2
    line (a.s.x,a.s.y)-(a.e.x,a.e.y),c
    line (b.s.x,b.s.y)-(b.e.x,b.e.y),c
    if c=1 then circle(hit.x,hit.y),4,4,,,,f
    screenunlock
  end if
wend
end
integer
Posts: 408
Joined: Feb 01, 2007 16:54
Location: usa

Post by integer »

Your cited source states this:

Code: Select all

   m2 = (float)1e+10;   // close enough to infinity
yours should probably use the equivalent

Code: Select all

   m2 = 1e+10     /' close enough to infinity '/

Also, your source has this comment:
// use Kramers rule to compute xi and yi
old Gabe Cramer, a brilliant swiss math man, sometime around
1750, developed what most call "Cramer's Rule" , and he
spelled his name with a 'C' (not a 'K')

After the declaration of the sub, the "as integer" WILL cause
a compiler error.

The algorithm you cite is correct.
KristopherWindsor
Posts: 2428
Joined: Jul 19, 2006 19:17
Location: Sunnyvale, CA
Contact:

Post by KristopherWindsor »

Pass the Point2d data Byref. The pointer takes fewer bytes than the data of the Point2d, so passing Byref should make the program copy less data for each Function call.
ytwinky
Posts: 217
Joined: Dec 03, 2005 12:44
Location: MD, Germany

Re: Line Intersection Algo.

Post by ytwinky »

Oz wrote:

Code: Select all

  if ( a.p1.x - a.p2.x ) <> 0 then
    m1 = ( a.p2.y - a.p1.y ) / ( a.p2.x - a.p1.x )
  else
    m1 = 1/0
  end if

  if ( b.p2.x - b.p2.x ) <> 0 then
    m2 = ( b.p2.y - b.p1.y ) / ( b.p2.x - b.p1.x )
  else
    m2 = 1/0
  end if
Shouldn't that be

Code: Select all

  if ( a.p2.x - a.p1.x ) <> 0 then
    m1 = ( a.p2.y - a.p1.y ) / ( a.p2.x - a.p1.x )
  else
    m1 = 1/0
  end if

  if ( b.p2.x - b.p1x ) <> 0 then
    m2 = ( b.p2.y - b.p1.y ) / ( b.p2.x - b.p1.x )
  else
    m2 = 1/0
  end if
?
Just to help me to understand your code ;-))
..and concerning 1/0: Why should the compiler show an error ?
The code is not executed at compile-time..
(I don't know if this is expressed correctly but I hope you can guess what I mean..)
regards
ytwinky
sir_mud
Posts: 1401
Joined: Jul 29, 2006 3:00
Location: US
Contact:

Post by sir_mud »

or you could reduce that down to one iif statement

Code: Select all

m1 = iif( (a.p2.y - a.p1.x) <> 0, (a.p2.y - a.p1.y) / (a.p2.x - a.p1.x ), 1/0 )
Oz
Posts: 586
Joined: Jul 02, 2005 14:21
Location: Waterloo, Ontario, Canada
Contact:

Post by Oz »

I didn't post any code of GameDev...that's someone elses code.

anyway, i updated the code in the first post.
i only want comments on optimizing...not critiquing my comments or whatever...you have to realize that when i post code, I don't care about the indents or the comments. All i care about is helpful feedback.

Oz

:: EDIT ::
ytwinky wrote:..and concerning 1/0: Why should the compiler show an error ?
technically, there wouldn't be a compile error, but I believe at runtime, it would cause an error because 1/0 is infinite.
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Post by D.J.Peters »

hello Oz what is with my version isn't it a helpful thing?

your gamedev.net example code will never return if two line hits or not !
it will calc the hitpoint if no intersection are heppents too.

Joshy
vdecampo
Posts: 2992
Joined: Aug 07, 2007 23:20
Location: Maryland, USA
Contact:

Post by vdecampo »

Since i'm not sure exactly what your trying to accomplish with your math I can't offer any optimizations there. But I would suggest passing your UDT's as pointers instead of ByVal. A copy of your UDT's is being made each time you enter the function.

I would sugest this...

Sub Line_Intersection(a As Line2d Ptr, b As Line2d Ptr, intersect As Point2d Ptr)

Then access the UDT's like...

With a[0]
If ( .p1.x - .p2.x ) <> 0 Then
etc...
End With

Also (at least in VB), using the With statement sped up things by decreasing the amount of dereferencing the compiler has to do to look up UDT elements.

Of course FB could be different in that respect, but it does improve readability. :-)

-Vince
Oz
Posts: 586
Joined: Jul 02, 2005 14:21
Location: Waterloo, Ontario, Canada
Contact:

Post by Oz »

In regards to FB, i don't think WITH will speed anything up, but I don't know too much of the inner workings of the compiler. I don't think it could slow it down, so I might as well...it improves readability, I suppose.

DJP, your example is good...i'll clock the two and see what ends up being quicker. I do like how it actually returns if there is an intersection or not; if you recall my original post had a sub returning an integer...originally, i wrote it as a function to return if there was an intersection, but got lazy.

Oz
h4tt3n
Posts: 698
Joined: Oct 22, 2005 21:12
Location: Denmark

Post by h4tt3n »

Oz, there's been posted quite a few really good explanations and code examples on line section intersection on this forum. Try to search for "line and intersection".
Dr_D
Posts: 2451
Joined: May 27, 2005 4:59
Contact:

Post by Dr_D »

h4tt3n wrote:Oz, there's been posted quite a few really good explanations and code examples on line section intersection on this forum. Try to search for "line and intersection".
hehehe... i was gonna suggest that too. ;)
Post Reply