Geek Answers Handbook

Point inside a rectangle with a two-dimensional axis, without branches

I am looking for the most optimized method to determine if a point is inside an axis-aligned rectangle.

The simplest solution is 4 branches (if), which is bad for performance.

+4
source share
5 answers

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

In the two-dimensional case, you need to do this twice, so this requires two conditions.

+7
source

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

Will work with both int and floating point.

+4
source

I think you will need four tests, no matter what, but if you know that a point is more likely inside or outside the rectangle, you can make sure that these four tests are performed only in the worst case.

If the probability that the point is 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 something really will be better ... (if you cannot make some assumption about where the edges of the rectangle are, as if they are aligned in 2s or something so scared)

+2
source

Many architectures support autonomous absolute value operation. If not, it can be modeled by multiplying or shifting the shifted sign value and believing in a specific behavior that depends on the implementation.

It is also quite possible that in Intel and ARM architectures the operation can be done without a wind

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

The reason is that range checking is often optimized for consistency:

 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

Bitwise and between (x) and (y) expressions are also not common.

EDIT Original idea:

This test range: a <= x <= b, first determine the midpoint. Then both sides can be tested with | (x-mid) | <A; multiplying with factor B that A has the strength of two ... (x-mid) * B <2 ^ n and squaring ((x-mid) * B) ^ 2 <2 ^ 2n

This value has only bits specified with the least significant 2n bits (if the condition is met). Do the same for the y and OR range. In this case, factor C should 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 AABB and nonzero for x, y outside. (Here the operation is or, since you are interested in the complement (a & b) and (c & d), which is (! (A & b)) | (! (C & dd));

+1
source

You do not tell us that you know about the range of possible values ​​and the required resolution, nor about what criteria you want to optimize.

The solution is to precompile the 2D Boolean array (if you can satisfy it) that you are looking for your coordinate pair. Costs 1 multiply (or shift), 1 add (to calculate the address) and 1 read memory.

Or two 1D boolean arrays. Costs 2 are added, two memory reads and 1 AND, with much smaller tables.

0
source

More articles:


All Articles