NewsForumsCodeLogsGallerySpecsSearch

Is there a func. to find if a point is in a rect?

BlitzMax Forums/BlitzMax Beginners Area/Is there a func. to find if a point is in a rect?

Smurftra(Posted 2006) [#1]
I know its easy to code, just wondering if its already in there.


tonyg(Posted 2006) [#2]
Nope


CS_TBL(Posted 2006) [#3]
this one doesn't use the x,y,w,h style but the x1,y1,x2,y2 style..

Function InBox:Int(x:Int,y:Int,x1:Int,y1:Int,x2:Int,y2:Int)
	If x>=x1 And x<=x2 And y>=y1 And y<=y2 Return 1 Else Return 0
End Function



Smurftra(Posted 2006) [#4]
I made my own, which is almost the same, mine is signed as a byte and returns true or false, which i find more convenient when reading code


Perturbatio(Posted 2006) [#5]
mine is signed as a byte


Byte types are slower than ints, if you plan on using it regularly in your game, you might want to consider adding an extra few bytes to your game's memory overhead by using Ints.


Smurftra(Posted 2006) [#6]
Really? Dang i have lots of code to change, im used to using bytes. I guess i can just search/replace byte by int. and i can still use true/false, right?


kronholm(Posted 2006) [#7]
yes


Leo Santos(Posted 2006) [#8]
Hey! Speaking about it...
If I have a field that can have only two states,(like true/false) is :INT really the BEST type to use?... isn't there something like a "boolean" type? (I looked in the docs, and didn't find anything).

I'm asking because I'm trying to keep the memory usage as low as possible... Yeah, I know, that's so Old School... :-)

Thanks!


CS_TBL(Posted 2006) [#9]
Dunno, test it.. benchmark!

But seriously.. memory? byte vs int differs 3 bytes per instance of that variable. In these days.. does it really matter? Typical shop-pc's come with 256mb, but most likely with 512mb mem, and some even with 1gb!

After all, we aren't using a z80 here with only 64kb to adress without bankswitching. :P


Dreamora(Posted 2006) [#10]
No there isn't anything like a boolean type and Int is definitely the best way to go (highest optimised type as current OS are 32Bit and int is faster than float)


CS_TBL(Posted 2006) [#11]
While talking bytes and ints, is ReadByte from a bank also slower than ReadInt? I can imagine mass-storage of bytes in a bank, while doing the math using ints..


H&K(Posted 2006) [#12]
64kb was loads.

I would recomend wrapping an Int, as a type Bool, cos then you get the benifits of a different type, yet the speed/size of an int


ImaginaryHuman(Posted 2006) [#13]
I just invented this:

Function InRect:Int(X:Int,Y:Int,X1PlusHalfWidth:Int,Y1PlusHalfHeight:Int,HalfWidth:Int,HalfHeight:Int)
   If Abs(X-X1PlusHalfWidth)<HalfWidth and Abs(Y-Y1PlusHalfHeight)<HalfHeight Then Return True Else Return False
End Function

I think it should work. No idea if it's faster or not, I am thinking it should be.

Requires the width and height of your rectangle to be even numbers if you want accuracy, otherwise may be 1 pixel off.

X1PlusHalfHeight is X1 (left edge of rect) plus half the width of the rect.
Y1PlusHalfHeight is Y1 (top edge of rect) plus half the height of the rect.
Of course HalfWidth is the width of the rect/2, and HalfHeight is half the height /2.

Maybe you can pass the parameters in an array or embedded in longs or as offsets in a bank or something, to speed it up a bit more.

Also if your collision rectangle is a perfect square, you can do this:
Function InSquare:Int(X:Int,Y:Int,X1PlusHalfSize:Int,Y1PlusHalfSize:Int,HalfSize:Int)
   If Abs(X-X1PlusHalfSize)<HalfSize and Abs(Y-Y1PlusHalfSize)<HalfSize Then Return True Else Return False
End Function



Smurftra(Posted 2006) [#14]
I fail to see how it would be faster unless you already store half width/heights and x + halfwidth etc... the fact you have to compute it to pass it to function costs more, doesnt it?


fredborg(Posted 2006) [#15]
You know you don't have to use any if's, you can just return the result. Like this:
Strict

Function RectsIntersect:Int(ax:Int,ay:Int,aw:Int,ah:Int,bx:Int,by:Int,bw:Int,bh:Int)

	Return (ax < (bx + bw)) & (ay < (by + bh)) & ((ax + aw) > bx) & ((ay + ah) > by)

End Function

Function PointInRect:Int(x:Int,y:Int,bx:Int,by:Int,bw:Int,bh:Int)

	Return (x < (bx + bw)) & (y < (by + bh)) & (x > bx) & (y > by)

End Function


'
' Beautiful test!
'

Graphics 640,480,0,0

Local x0:Int = 100
Local y0:Int = 100
Local w0:Int = 200
Local h0:Int = 150

Local x1:Int = Rand(0,540)
Local y1:Int = Rand(0,380)
Local w1:Int = 100
Local h1:Int = 100

Local sx:Int = 1
Local sy:Int = 1

Local x2:Int = MouseX()
Local y2:Int = MouseY()

While Not (KeyHit(KEY_ESCAPE) Or AppTerminate())

	x1:+sx
	y1:+sy
	
	If x1+w1>640 Then sx = -1
	If x1<0		 Then sx = 1
	If y1+h1>480 Then sy = -1
	If y1<0		 Then sy = 1

	x2 = MouseX()
	y2 = MouseY()

	Cls

	SetColor 255,0,0
	DrawRect x0,y0,w0,h0
	
	SetColor 0,255,0
	DrawRect x1,y1,w1,h1

	SetColor 255,255,0
	Plot x2,y2

	SetColor 255,255,255
	If RectsIntersect(x0,y0,w0,h0,x1,y1,w1,h1)
		DrawText "RectsIntersect",0,0
	EndIf
	If PointInRect(x2,y2,x0,y0,w0,h0)
		DrawText "PointInRect",0,20
	EndIf
	
	Flip	

Wend
That's about as fast as it gets.


ImaginaryHuman(Posted 2006) [#16]
Nice fredborg, I did wonder if you could just return a value instead of doing an If.

Function InRect:Int(X:Int,Y:Int,X1PlusHalfWidth:Int,Y1PlusHalfHeight:Int,HalfWidth:Int,HalfHeight:Int)
   Return (Abs(X-X1PlusHalfWidth)<HalfWidth) & (Abs(Y-Y1PlusHalfHeight)<HalfHeight)
End Function

Might be a bit faster. If for some reason you know that a big group of rects will be a given size you could just hardcode it for that size rather than passing variables.

As to your question Smurf, you'd have to have your four variables precomputed in some kind of array or something. If you need them to be dynamic in realtime then do some other method, so you can move the rects, then just do:
Function InRect:Int(X:Int,Y:Int,X1:Int,Y1:Int,HalfWidth:Int,HalfHeight:Int)
   Return (Abs(X-(X1+HalfWidth))<HalfWidth) & (Abs(Y-(Y1+HalfHeight))<HalfHeight)
End Function

I'm gunna have to test this fredborg to see which is faster ;-D


ImaginaryHuman(Posted 2006) [#17]
I did a speed comparison between my final InRect() function (the flexible one), and fredborg's code.

Fredborg your code took 4518 millisecs to do 10 million calls. My code took 4662. Yours is very slightly faster. Not all the time though. Sometimes I got better numbers on mine, not sure why.

My fixed-position code is about 4620 - getting closer. Strangely my square routine is a bit slower than my rect one. lol

But anyway, yes, Fredborg, congrats, your routine is actually the fastest so far (just ;-D)

Although THIS:
Function PointInRect:Int(x:Int,y:Int,bx:Int,by:Int,bx2:Int,by2:Int)

        Return (x < bx2) & (y < by2) & (x > bx) & (y > by)

End Function


should be faster still. (It is, 4543 millisecs :-)

Interestingly >= and <= are slower than > and <.


fredborg(Posted 2006) [#18]
:)

I guess by passing all the parameters as variable pointers you could speed it up ever so slightly. Otherwise every parameter is recreated as a local variable to the function, which is probably not healthy for the cpu. Try this:
Function RectsIntersect:Int(ax:Int Var,ay:Int Var,aw:Int Var,ah:Int Var,bx:Int Var,by:Int Var,bw:Int Var,bh:Int Var)

	Return (ax < (bx + bw)) & (ay < (by + bh)) & ((ax + aw) > bx) & ((ay + ah) > by)

End Function

Function PointInRect:Int(x:Int Var,y:Int Var,bx:Int Var,by:Int Var,bw:Int Var,bh:Int Var)

	Return (x < (bx + bw)) & (y < (by + bh)) & (x > bx) & (y > by)

End Function
Actually, just tested it, and it seems like that was a false statement... On my machine it is ever so slightly slower.

It does however seem that logical and (And) is faster than binary and (&), so try replacing those :)


ImaginaryHuman(Posted 2006) [#19]
plus its faster if you dont use a width,height, but use an x2,y2 instead because you can remove the adds.


Shambler(Posted 2006) [#20]
I would use an early out test, should be faster on average depending on how large the Rect is compared to the screen res.

Function InRect:Int(x:Int,y:Int,x1:Int,y1:Int,x2:Int,y2:Int)
	If x1>x Return False
	If x2<x Return False
	If y1>y Return False
	If y2<y Return False
	Return True
End Function



Shagwana(Posted 2006) [#21]
Not strickly bmax, but heres my fastest one for bb3d -> http://www.blitzbasic.com/codearcs/codearcs.php?code=118

Im sure that converted to bmax would be fast :)


Dreamora(Posted 2006) [#22]
Yepp seems so :-)


Strict
Function DetectPointInsideRect(iPointX:Int,iPointY:Int,iXPos1:Int,iYPos1:Int,iXPos2:Int,iYPos2:Int)
	Return ((((iPointX-iXPos1) ~ (iPointX-iXPos2)) & ((iPointY-iYPos1) ~ (iPointY-iYPos2))) & $80000000)
End Function 

Function PointInRect:Int(x:Int,y:Int,bx:Int,by:Int,bw:Int,bh:Int)

	Return (x < (bx + bw)) &(y < (by + bh)) &(x > bx) And (y > by)

End Function


Graphics 640,480,0,0

Local x0:Int = 100
Local y0:Int = 100
Local w0:Int = 200
Local h0:Int = 150


Local x1:Int = x0+w0
Local y1:Int = y0+h0
Local w1:Int = 100
Local h1:Int = 100

Local sx:Int = 1
Local sy:Int = 1

Local x2:Int = Rand(0,639)
Local y2:Int = Rand(0,479)

Local t1:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	PointInRect(x2,y2,x0,y0,w0,h0)
Next

t1	= MilliSecs() - t1

Local t2:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	DetectPointInsideRect(x2,y2,x0,y0,x1,y1)
Next

t2	= MilliSecs() - t2

Print "Fredborg: " + t1
Print "Shagwana: " + t2



Fredborg: 4205
Shagwana: 4178


What I have not tested thought is if the result is correct.
And fredborg: On my system, & is faster than and ...


ImaginaryHuman(Posted 2006) [#23]
I find it interesting that these functions aren't really all that much different in speed. I think there must be a lot of overhead with the function call itself, passing of parameters, and the return of data.

To be honest, this one-liner piece of code is something that I would inline into my overall program, rather than having a whole function call wrapped around it. I bet that's a lot faster.


CS_TBL(Posted 2006) [#24]
All these kinda practical and handy small functions should have been in the default bmax commandset, imho..


Dreamora(Posted 2006) [#25]
Angel: That indeed is an idea ... inline ... ;-)

Result: MingW 5 just is too optimized *hehe*


Strict
Import "inrect.c"
Extern
	Function PointInRect:Int(x:Int,y:Int,bx:Int,by:Int,bw:Int,bh:Int)
	Function DetectPointInsideRect:Int(iPointX:Int,iPointY:Int,iXPos1:Int,iYPos1:Int,iXPos2:Int,iYPos2:Int)
End Extern

Function DetectPointInsideRect1(iPointX:Int,iPointY:Int,iXPos1:Int,iYPos1:Int,iXPos2:Int,iYPos2:Int)
	Return ((((iPointX-iXPos1) ~ (iPointX-iXPos2)) & ((iPointY-iYPos1) ~ (iPointY-iYPos2))) & $80000000)
End Function 


Function PointInRect1:Int(x:Int,y:Int,bx:Int,by:Int,bw:Int,bh:Int)

	Return (x < (bx + bw)) & (y < (by + bh)) & (x > bx) & (y > by)

End Function




Local x0:Int = 100
Local y0:Int = 100
Local w0:Int = 200
Local h0:Int = 150


Local x1:Int = x0+w0
Local y1:Int = y0+h0
Local w1:Int = 100
Local h1:Int = 100

Local sx:Int = 1
Local sy:Int = 1

Local x2:Int = Rand(0,639)
Local y2:Int = Rand(0,479)

Local t1:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	PointInRect1(x2,y2,x0,y0,w0,h0)
Next

t1	= MilliSecs() - t1

Local t2:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	PointInRect(x2,y2,x0,y0,w0,h0)
Next

t2	= MilliSecs() - t2


Local t3:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	DetectPointInsideRect(x2,y2,x0,y0,x1,y1)
Next

t3	= MilliSecs() - t3

Local t4:Int = MilliSecs()
For Local i = 1 To 10000000
	x2 = Rand(0,639)
	y2 = Rand(0,479)
	DetectPointInsideRect1(x2,y2,x0,y0,x1,y1)
Next

t4	= MilliSecs() - t4

Print "Fredborg BM: " + t1
Print "Fredborg Inline: " + t1
Print "Shagwana Inline: " + t3
Print "Shagwana BM: " + t4


with inrect.c
inline int DetectPointInsideRect(int iPointX,int iPointY,int iXPos1,int iYPos1,int iXPos2,int iYPos2)
{
	return ((((iPointX-iXPos1) ^ (iPointX-iXPos2)) & ((iPointY-iYPos1) ^ (iPointY-iYPos2))) & 0x80000000);
}

inline int PointInRect(int x, int y, int bx, int by, int bw, int bh)
{
	return (x < (bx + bw)) & (y < (by + bh)) & (x > bx) & (y > by);
}


Gives the results:

Fredborg BM: 4103
Fredborg Inline: 4103
Shagwana Inline: 4070
Shagwana BM: 4081

This means around 0.0004081 ms per function call.
Don't know, how fast can a 1.5 Ghz P-M Banias be?

But I might try it again when my new system arives which has a far better math unit (Banias were the first P-M with not a that good math unit - my new system is a 2Ghz Core Duo ... 150-200% as fast ... per core)


Smurftra(Posted 2006) [#26]
Very interesting thread. Fun to see the different solutions to such a small problem


ImaginaryHuman(Posted 2006) [#27]
It is cool figuring out optimizations, like the old days when it actually mattered to get things to be as fast and efficient as possible. People these days are spoilt and lazy ;-)

Jokin'.


How fast is Shambler's early-out code?


Dreamora(Posted 2006) [#28]
Problem ist, most old optimations are useless today.
I spend 2 hours on searching different sqr optimations. Result: Even mingW 3.1 has a default sqr functionality that is faster *lol* Haven't tested with MingW 5 yet, but would assume that it is even faster


The early out is slower against all 4 tests I did above (200ms+)... That has to do with the fact that BM does early out as well.
if the (a and b and c) sees that a is false it returns false and does not parse further. As it does return true if (a or b or c) with a true.


Haramanai(Posted 2006) [#29]
Just for the record guys.
I don't wand to sound like a bad guy but...
Collision detection it's really old and this kind of thing you are trying to do it's point in an AABB.
What is AABB?
axis aligned bounding box
What is this?
It's a box that have it's edges alinged to the axis of the coordinates space.
So this box never rotate and blah blah blah...
I just wanted to say this cause if you really wand to learn stuf like this you must know what you are searching for. And for collision detection, AABB it's the best place to start with.


tonyg(Posted 2006) [#30]
... which is a bit overkill if you just want to check if your mouse pointer is within a particular rectangular area.


Haramanai(Posted 2006) [#31]
Yes for sure. But the best answer for speed was posted in the third post by CS_TBL . If you wand speed and you have static boxies you better store the points of the boxies.
Another thing it's that sometime it's better to use circle.
Why? it's really faster. You have to change only one point per loop. If you have stored the square radius you way off for speed even for an old commondore.


tonyg(Posted 2006) [#32]
Another thing it's that sometime it's better to use circle.

Afaik, that's what this thread has been about since the original post was answered.
How about providing some code so it can be stuck into the benchmark test?
The quickest I've found is just to move the function into the mainloop code (think somebody else mentioned it before).


Haramanai(Posted 2006) [#33]
Well just a rough code of what i remember so don't shoot me.


I may be wrong about the speed... I am waiting for your tests.


tonyg(Posted 2006) [#34]
Hmmm, I wasn't sure I understood what you meant in the first place.
Testing circle/circle or point/circle isn't the same as point/rectangle so I'm not sure how they're to be compared.
Not sure what tests you're expecting me to carry out but taking the function code and placing it in the 'mainloop' speeds things up quite dramatically as per AngelDaniel's suggestion.


ImaginaryHuman(Posted 2006) [#35]
I'm not sure what you were saying about collision detection being `really old`. I don't see that it's aged at all. It's still needed now as much as it ever was.


Haramanai(Posted 2006) [#36]
What I wanted to say is that you were trying to solve an old problem and that was point in an AABB. and you had a topic without even talking about it. Someone who may want to search and read about similar things will be more lucky if he search for: AABB collision detection.

AngelDaniel saying that something it's old does not mean that it's out of use. Means that you can find information if you find the right direction. And this is what I tryed to say.


ImaginaryHuman(Posted 2006) [#37]
Old can imply out of use, which it did, and not many people will know of the term AABB, only those who already know about it, and they probably don't need this thread.