CODEWITHSUNDEEP
algorithm
JiminP
JiminP

Reputation: 2142

Is there any clever way to determine whether a point is in a rectangle?

I want to calculate whether a point, (x,y), is inside a rectangle which is determined by two points, (a,b) and (c,d).

If a<=c and b<=d, then it is simple:

a<=x&&x<=c&&b<=y&&y<=d

However, since it is unknown whether a<=c or b<=d, the code should be

(a<=x&&x<=c||c<=x&&x<=a)&&(b<=y&&y<=d||d<=y&&y<=b)

This code may work, but it is too long. I can write a function and use it, but I wonder if there's shorter way (and should be executed very fast - the code is called a lot) to write it.

One I can imagine is:

((c-x)*(x-a)>=0)&&((d-y)*(y-b)>=0)

Is there more clever way to do this?

(And, is there any good way to iterate from a from c?)

Upvotes: 1

Views: 158

Answers (4)

AnT stands with Russia
AnT stands with Russia

Reputation: 320709

While sorting the (a, b) and (c, d) pairs as suggested in the accepted answer is probably the best solution in this case, an even better application of this method would probably be to elevate the a < b and c < d requirement to the level of the program-wide invariant. I.e. require that all rectangles in your program are created and maintained in this "normalized" form from the very beginning. Thus, inside your point-in-rectangle test function you should simply assert that a < b and c < d instead of wasting CPU resources on actually sorting them in every call.

Upvotes: 1

kevin cline
kevin cline

Reputation: 2746

I like the this:

((c-x)*(x-a)>=0)&&((d-y)*(y-b)>=0)

but with more whitespace and more symmetry:

(c-x)*(a-x) <= 0 && (d-y)*(b-y) <= 0

It's mathematically elegant, and probably the fastest too. You will need to measure to really determine which is the fastest. With modern pipelined processors, I would expect that straight-line code with the minimum number of operators will run fastest.

Upvotes: 3

John Kugelman
John Kugelman

Reputation: 362007

Swap the variables as needed so that a = xmin and b = ymin:

if a > c: swap(a,c)
if b > d: swap(b,d)

a <= x <= c and b <= y <= d

Shorter but slightly less efficient:

min(a,c) <= x <= max(a,c) and min(b,d) <= y <= max(b,d)

As always when optimizing you should profile the different options and compare hard numbers. Pipelining, instruction reordering, branch prediction, and other modern day compiler/processor optimization techniques make it non-obvious whether programmer-level micro-optimizations are worthwhile. For instance it used to be significantly more expensive to do a multiply than a branch, but this is no longer always the case.

Upvotes: 3

Niet the Dark Absol
Niet the Dark Absol

Reputation: 324790

Define intermediary variables i = min(a,b), j = min(c,d), k = max(a,b), l = max(c,d)
Then you only need i<=x && x<=k && j<=y && y<=l.

EDIT: Mind you, efficiency-wise it's probably better to use your "too long" code in a function.

Upvotes: 0

Related Questions