CODEWITHSUNDEEP
c++calgorithm
jmasterx
jmasterx

Reputation: 54123

Point in axis aligned rectangle test?

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.

Upvotes: 2

Views: 3404

Answers (5)

floppybunny
floppybunny

Reputation: 11

I have found two better answers while coding for a contest. First, it uses coordinates for both points, rather than height/width which is slow, also this assumes a point is two floats and a rect is four floats; for different data types this logic might need to be changed!

First, using a compiler that knows Intel SSE instructions, a test that combines the & and && in the right way is quite a bit faster. This combines two tests into one, but keeps the quick out for the second two tests:

if((p.x>=r.lx)&(p.x<=r.hx)&&(p.y>=r.ly)&(p.y<=r.hy))
    ptisinrect=true;

Currently, compiling using the 128 bit SSE instructions this is faster than all &&'s, but using the 256 bit AVX2 setting was slower, even with all &'s.

However, if you set up your program to test lots of points in an array, you can get it to fully vectorize and the a dramatic performance improvement (still with SSE, not AVX or AVX2). Vectorization is a simplistic parallelization that has some strict requirements. For example, there can be no short circuits in the loop, and you cant save to the same variable more than once.

So take look at this simplified example of non-vectorized code that looks for 'count' ptinrects and exits if enough are found:

for(unsigned a=0;a<n;++a)
{
    if((pp[a].x>=r.lx)&&(pp[a].x<=r.hx)&&(pp[a].y>=r.ly)&&(pp[a].y<=r.hy))
    {
        ++found;
       if(found>count)
            return true;
    }

}

The following code is an example of the same thing, only vectorizing a search of 0 to n ptinrects, but still exiting when 'count' points in the rectangle are found. Note that this code may read-access 32 points past n, so the array needs to be allocated with 32 extra points of space:

typedef struct ab
{
    int64_t a[4];
};
typedef struct{
union{
    ab ab;
    int8_t o[32];
    };
}xmmb;
xmmb o;
for(unsigned i=0;i<n;i+=32)
{
    for(unsigned a=0;a<32;++a)
    {
        o.o[a]=((pp[i+a].x>=r.lx)&(p[i+a].x<=r.hx)&(p[i+a].y>=r.ly)&(p[i+a].y<=r.hy));
    }

    for(unsigned kk=0;kk<4;++kk)
    {
        if(o.ab.a[kk])
       for(unsigned a=kk<<3;a<(kk+1)<<3;++a)
       {
            if(o.o[a]) 
            {
                if(i+a<n)
                {
                    ++found;
                    if(found>count)
                        return true;
                }
            }
        }
    }
}

Even though it is quite bizarre looking, this code is MUCH faster than the previous example! What it is doing is running the ptrect tests in vector-parallel and storing the true/false in an array of 32 8bit-bytes. Then it checks 8 of those at a time (thus the union with 4 64-bitints) to save tests. Then looks at any that had a true value and adds them into the count.

Again, note that this only works with 128-bit SSE, and is currently (feb 2015) slower when compiled for 256-bit AVX2, so use switchs or pragmas to keep it SSE Finally, this code might have syntax errors and the like because entering it into this format was not cut-n-paste easy :D

tags: fast ptinrect fast pointinrect fast point in rectangle

Upvotes: 1

Paul R
Paul R

Reputation: 212979

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

Upvotes: 0

Benjamin Lindley
Benjamin Lindley

Reputation: 103713

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.

Upvotes: 6

Arun
Arun

Reputation: 20383

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

Upvotes: 1

JoshD
JoshD

Reputation: 12814

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.

Upvotes: 1

Related Questions