5

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.

1
  • This is not a C question, because you are interested in branches in the machine code, not branches in the conceptual C machine, and because the C standard generally does not address performance. Optimizing code is highly platform specific, so you should state what platform this is for. Some processors have instructions that perform compares and return results in registers, and those results can be ANDed to get a final result. Commented Dec 3, 2012 at 14:17

5 Answers 5

8

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.

2
  • Excellent. Logical AND + shifting ((unsigned)(exp1&exp2))>>31 should complete the trick. Commented Dec 3, 2012 at 14:41
  • @AkiSuihkonen: I don't think that can be easyly, portably and efficiently done for float point values.
    – salva
    Commented Dec 3, 2012 at 15:09
5

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.

2

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)

4
  • Shortcut boolean expression looks indeed attractive as it allows performing partial evaluation. Unfortunately, when implemented with branches, it is very inefficient as it breaks the fetch/execute pipeline, with strongly unpredictable jumps. And if implemented with conditional instructions, they are anyway all executed :(
    – user1196549
    Commented Dec 3, 2012 at 15:11
  • Anyway, it is worth to note here that the order of the comparisons is not totally unimportant.
    – user1196549
    Commented Dec 3, 2012 at 15:14
  • 1
    Assuming that the target rectangle is tiny in comparison to the spread of the points, a first test on X will settle about half of the cases; then a second test on X settles about all of the remaining cases, giving an average of 3/2 comparisons per point. On the other hand, performing the second test on Y only settles half of the remaining cases, requiring an additional test for yet another half, giving an average of 7/4 comparisons per point. When the rectangle is large compared to the spread of the points, all 4 tests are required.
    – user1196549
    Commented Dec 3, 2012 at 15:28
  • There is also a more exotic solution which reduces the worst-case number of tests (sorry for being so wordy): first check on what side of the diagonal the point lies (takes one comparison); then, in at most two comparisons you can tell inside or outside the rectangle. Worst case 3 comparisons, average case 9/4 for a tiny rectangle.
    – user1196549
    Commented Dec 3, 2012 at 18:10
1

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));

0

You don't tell us what you know about the range of possible values and resolution required, nor on what criterion you want to optimize.

A solution is to precompute a 2D array of booleans (if you can affort it) that you look-up for your pair of coordinates. Costs 1 multiply (or shift), 1 add (for address computation) and 1 memory read.

Or two 1D arrays of booleans. Costs 2 adds, two memory reads and 1 AND, with much smaller tables.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.