My rectangle structure has these members: x, y, width, height.
Given a point x, y what would be the fastest way of knowing if x, y is inside of the rectangle? I will be doing lots of these so speed is important.
+1
A:
if (p.x > x && p.y > y && p.x < x+width && p.y < y+height)
This should only be a handful of assembly instructions.
It assumes that x, y of the rectangle are always the smallest value coordinates of the rectangle. It also discounts points that are on the border of the rectangle.
JoshD
2010-10-08 20:14:30
It *may* go faster if, instead of logic operators, you used bitwise ones: the comparisons are really cheap, and I think that even doing all of them may be faster than to add three branches. But, as usual, profiling is the only way to know.
Matteo Italia
2010-10-08 20:43:19
+1
A:
In C++ (can be trivially translated to C):
bool pointInRectangle( Point const & p, Rectangle const & r ) {
return
((r.x <= p.x) && (p.x <= (r.x + r.width ))) &&
((r.y <= p.y) && (p.y <= (r.y + r.height)));
}
ArunSaha
2010-10-08 20:29:23
@JoshD: Thats true. I never remember the precedence things.. so, to avoid any confusion for me as well as the reader, I always put parentheses liberally :).
ArunSaha
2010-10-08 20:42:19
@ArunSaha: But you're pretty confident that the dot operator goes before addition :D (Sorry, I couldn't help myself.)
JoshD
2010-10-08 20:47:44
@ArunSaha For what it's worth, I'd say going this extreme borders on making it more confusing and less readable. While in this case it's fairly obvious what's going on, if it instead was something complex where a couple of the parentheses were purposefully inhibiting normal precedence, then those important parentheses would almost be lost amongst all the redundant ones.
TheUndeadFish
2010-10-08 21:13:11
+4
A:
This is how I usually do it. Given a point that is outside of the rectangle, this will do fewer tests in 3 out of 4 cases. And sometimes only one test is done.
if(point.x < rect.x) return false;
if(point.y < rect.y) return false;
if(point.x >= rect.x + rect.width) return false;
if(point.y >= rect.y + rect.height) return false;
return true;
Which one you use should be dependent upon whether you anticipate more collisions or more misses.
PigBen
2010-10-08 20:46:59
A:
If you're targetting a specific CPU, e.g. x86, the you can use SIMD (i.e. SSE) to do a very fast branchless test. The trick is to use 4 x 32 bit ints to represent the rectangle, which maps to a SIMD vector (it needs to be 16 bytes in size and 16 byte aligned).
Paul R
2010-10-08 21:07:02