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.

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
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,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
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:
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
Location: Waterloo, Ontario, Canada
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[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:
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. ;)

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 3 guests