Line Intersection Algo.

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

Line Intersection Algo.

Postby Oz » Aug 12, 2007 1:17

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

Postby Merick » Aug 12, 2007 2:28

m1 = 1/0????

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

Postby D.J.Peters » Aug 12, 2007 4:03

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: 388
Joined: Feb 01, 2007 16:54
Location: usa

Postby integer » Aug 12, 2007 4:36

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:

Postby KristopherWindsor » Aug 12, 2007 4:48

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.

Postby ytwinky » Aug 12, 2007 7:41

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:

Postby sir_mud » Aug 12, 2007 8:58

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: 585
Joined: Jul 02, 2005 14:21
Location: Waterloo, Ontario, Canada
Contact:

Postby Oz » Aug 12, 2007 17:54

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: 8023
Joined: May 28, 2005 3:28
Contact:

Postby D.J.Peters » Aug 12, 2007 18:02

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: 2982
Joined: Aug 07, 2007 23:20
Location: Maryland, USA
Contact:

Postby vdecampo » Aug 12, 2007 19:47

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: 585
Joined: Jul 02, 2005 14:21
Location: Waterloo, Ontario, Canada
Contact:

Postby Oz » Aug 12, 2007 20:33

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: 693
Joined: Oct 22, 2005 21:12
Location: Denmark

Postby h4tt3n » Aug 12, 2007 21:17

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: 2396
Joined: May 27, 2005 4:59
Contact:

Postby Dr_D » Aug 12, 2007 22:00

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. ;)

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 3 guests