## Line Intersection Algo.

Oz
Posts: 585
Joined: Jul 02, 2005 14:21
Contact:

### Line Intersection Algo.

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 singleEnd TypeType Line2d  p1 as Point2d  p2 as Point2dEnd TypeSub 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
m1 = 1/0????

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

Code: Select all

`type point2d  as integer x,yend typetype line2d  as point2d s,e ' start-endend typefunction 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  endifend function' maindim as line2d  a,bdim as point2d hitdim as integer ca.s.x=480:a.s.y=120a.e.x=160:a.e.y=360screenres 640,480while 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 ifwendend`
integer
Posts: 388
Joined: Feb 01, 2007 16:54
Location: usa

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:
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.

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