Interesting speed test

I've tested two different versions of LinesCollide. The method is pretty the same (solving line-equatations). Version 1 (LinesCollide) calculates everything and then finally determine if the lines collide.

Version 2 (LinesCollide2) tries to calculate only the neccessary to leave the function as fast as possible before everything is calculated. Less calculation, more if-then-else.

I've called both versions with 500k random lines (same seed for both), and LinesCollide (=calc everything, only one if) was always faster (750ms against 790ms for LinesCollide2). That's with debug off.

I personally thought that version 2 would be faster, at least with debug off.

If you want to try by yourself:

superstrict
'graphics 800,600

global _x1#,_x2#,_x3#,_x4#
global _y1#,_y2#,_y3#,_y4#

global time1%,count1%
global time2%,count2%

seedrnd (123456)
delay(2000)
time1=millisecs()
for local i%=1 to 500000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	if LinesCollide(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) then count1:+1
Next
time1=millisecs()-time1
print "Method 1: "+count1+" colisions found in "+time1+" ms"

seedrnd (123456)
time2=millisecs()
for local i%=1 to 500000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	if LinesCollide2(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) then count2:+1
Next
time2=millisecs()-time2
print "Method 2: "+count2+" colisions found in "+time2+" ms"
delay(1000)
end


function LinesCollide%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	local dpx#= x3 - x1 + x4 - x2
	local dpy#= y3 - y1 + y4 - y2
	local qax#= x2 - x1
	local qay#= y2 - y1
	local qbx#= x4 - x3
	local qby#= y4 - y3
	
	local d#= qay*qbx - qby*qax
	local la# = qbx*dpy - qby*dpx
	local lb# = qax*dpy - qay*dpx
	
	if abs(la)<=abs(d)  and abs(lb) <=abs(d) then return true
	return false
End Function

function LinesCollide2%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	local LowerX#,UpperX#,LowerY#,UpperY#
	local Ax#,Ay#,Bx#,By#,Cx#,Cy#,d#,e#,f#
  	
	Ax# = x2 - x1
  	Bx# = x3 - x4
	if Ax<0.0
		LowerX = x2
		UpperX = x1
	else
		UpperX = x2
		LowerX = x1
	end if

	if Bx>0.0
		if UpperX<x4 or x3<LowerX then return false
	elseif (UpperX<x3 or x4<LowerX)
		return false
	endif
  
	Ay = y2 - y1
	By = y3 - y4

	if Ay<0.0
		LowerY = y2
		UpperY = y1
	else
		UpperY = y2
		LowerY = y1
	end if

	if By>0.0
		if UpperY<y4 or y3<LowerY then return false
	elseif UpperY<y3 or y4<LowerY
		return false
	endif

	Cx = x1 - x3
	Cy = y1 - y3
  	d  = (By * Cx) - (Bx * Cy)
  	f  = (Ay * Bx) - (Ax * By)

	if f>0.0
		if d<0.0 or d>f then return false
	elseif d>0.0 or d<f
		return false
	endif

 	e = (Ax * Cy) - (Ay * Cx)

	if f>0.0 then
		if e<0.0 or e>f then return false
	elseif e>0.0 or e<f then
		return false
	endif

  	return true
end function