Point inside 2D axis aligned rectangle, no branches

Question

I'm searching for the most optimized method to detect whether a point is inside an axis aligned rectangle.

The easiest solution needs 4 branches (if) which is bad for performance.

Answer 1

Given a segment [x0, x1], a point x is inside the segment when (x0 - x) * (x1 - x) <= 0.

In two dimensions case, you need to do it twice, so it requires two conditionals.

Answer 2

Consider BITWISE-ANDing the values of XMin-X, X-XMax, YMin-Y, Y-YMax and use the resulting sign bit.

Will work with both ints and floats.

Answer 3

I think you will need the four tests no matter what, but if you know if the point is more likely to be in or out of the rectangle, you can make sure those four tests are only run in the worst case.

If the likelihood of the point being inside is higher, you can do

if ((x>Xmax) || (x<Xmin) || (y>Ymax) || (y<Ymin)) {
 // point not in rectangle
}

Otherwise, do the opposite:

if ((x<=Xmax) && (x>=Xmin) && (y<=Ymax) && (y>=Ymin)) {
 // point in rectangle
}

I am curious if really there would be anything better... (unless you can make some assumption on where the rectangle edges, like they are align to power of 2s or something funky like that)

Answer 4

Many architectures support branchless absolute value operation. If not, it can be simulated by multiplication, or left shifting a signed value and having faith on particular "implementation dependent" behaviour.

Also it's quite possible that in Intel and ARM architectures the operation can be made branchless with

((x0<x) && (x<x1))&((y0<y) && (y<y1))

The reason is that the range check is often optimized to a sequence:

mov ebx, 1       // not needed on arm
sub eax, imm0    
sub eax, imm1    // this will cause a carry only when both conditions are met
cmovc eax, ebx   // movcs reg, #1    on ARM

The bitwise and between (x) and (y) expressions is also branchless.

EDIT Original idea was:

Given test range: a<=x<=b, first define the middle point. Then both sides can be tested with |(x-mid)| < A; multiplying with a factor B to have A a power of two... (x-mid)*B < 2^n and squaring
((x-mid)*B)^2 < 2^2n

This value has only bits set at the least significant 2n bits (if the condition is satisfied). Do the same for range y and OR them. In this case the factor C must be chosen so that (y-midy)^2 scales to the same 2^2n.

 return (((x-mid)*B)*(((x-mid)*B) | ((y-mid)*C)*((y-mid)*C))) >> (n*2);

The return value is 0 for x,y inside the AABB and non-zero for x,y outside. (Here the operation is or, as one is interested in the complement of (a&&b) & (c&&d), which is (!(a&&b)) | (!(c&dd));