how to determine whether a point lies inside a rectangle?

Question

Possible Duplicate:
Finding whether a point lies inside a rectangle or not

There is an interview question that is, "How to determine whether a point lies inside a rectangle"

Note that the rectangle could be rotated as well. So the simple solution of checking point inside the rectangle doesn't stands valid here...

Please share your thoughts on this question..

I found a link on internet, and was trying to understand it, but failed.... Please if any body out here can give complete solution with bit of computer graphics logic, because i have forgotten all the basics.... How to determine if a point is inside rectangle.

These kinds of interview questions are not about answers or they wouldn't be so vague. They are just curious how you think and how well you communicate what those thoughts are ... — AJG85, May 18 '11 at 15:41
Might prove helpful: http://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not/2752753#2752753 — Platinum Azure, May 18 '11 at 15:52
What are you given? The coordinates of the four (or three) points? One point and two edges? Two opposite points and a line? Your question does not state anything. — sawa, May 19 '11 at 02:58

Jerry Coffin · Answer 1 · 2011-05-18T18:33:15.330

16

Pick a point that's definitely outside the rectangle. Then create a segment from that point to the point in question. Solve the linear equations for intersections between that segment and the segments that make up the rectangle. If you get exactly one intersection, the point is inside the rectangle. Otherwise (0 or 2 intersections), it's outside.

This is trivial to extend to essentially any polygon -- an odd number of intersections means the point is inside the polygon, and an even number means it's outside.

Edit: It may not be immediately obvious, so I'll emphasize that the point we pick outside the rectangle (polygon) is entirely arbitrary. We can pick whatever point we want as long as we're sure it's outside the polygon. To keep our computations easy, what we'll typically do is pick (P_x, infinity) (where P_x is the x coordinate of the point P that we're testing) -- that is, what we're creating is essentially a vertical ray. That simplifies testing a bit, because we only have to test against one end-point to find an intersection. It also simplifies solving the linear equations to the point that it's barely recognizable as solving linear equations anymore. We really just need to compute the Y coordinate for the line at the P_x, and see if it's greater than P_y. As such, solving the linear equation breaks down to:

checking whether that X value is within the range of X values for the segment
if it is, plugging the X value into the equation of the line
testing whether the resulting Y value is greater than P_y

If those pass, we have an intersection. Also note that the tests can be carried out in parallel (handy if we're doing this on parallel hardware like a GPU).

edited May 18 '11 at 18:33

answered May 18 '11 at 15:47

Jerry Coffin

476,176
80
629
1,111

1

This might be the best answer here. (+1) – Platinum Azure May 18 '11 at 15:56
1

Read mine before you say that. :) – R.. GitHub STOP HELPING ICE May 18 '11 at 16:09
2

When the segment goes through a corner, things get complicated. The segment could either go inside or stay outside (only "touching" the rectangle in one point), and you can't easily decide between the two. – Sjoerd May 18 '11 at 16:19
@R. IMO, your solution is great mathematically, but I can't quite imagine using it in most real code. First, it requires a representation that would be pretty unusual for the task as stated. Second, I doubt more than one out of 20 maintenance programmers would understand it *at all*. Deep in a geometry engine that would only ever be touched by real experts, it might be fine. In most typical code, I'd normally prefer something a bit more intuitive. – Jerry Coffin May 18 '11 at 16:29
Well, I think you could simplify it down to a few lines of code, even converting from a "more typical" representation, and then just a meaningful function name and a comment would be enough to keep anyone from needing to look at the internals if they don't understand geometry... – R.. GitHub STOP HELPING ICE May 18 '11 at 16:39
A good approach for arbitrary polygons! For a simple rectangle however, my answer provides a simpler solution with only one set of linear equations to solve. – groovingandi May 18 '11 at 16:52
@R: the problem is that if you do the conversion for just this operation, I'm pretty sure it ends up slower. Keep in mind that the linear equations above are quite trivial. Even at best, *nearly* the only way your method gets a real gain is when you get an "early elimination" so you avoid solving for all four sides. – Jerry Coffin May 18 '11 at 16:59
@R. We're left with two choices: either use that representation almost throughout, and probably rather difficult maintenance, or else don't use it at all. There *might* (just barely) be a tiny bit of middle ground, but for this one operation it strikes me as a pretty serious loss of understandability for a gain in efficiency that's likely to be minimal at best. – Jerry Coffin May 18 '11 at 17:11
If you're just testing click locations in a UI, it's probably not necessary to optimize anyway, but if this has something to do with simulation/game physics, it may very well be a major bottleneck. I don't think storing rectangles as an orientation vector `(x,y)` (with a second implied normal `(-y,x)`) and intervals along each of these vectors is a very confusing or unusual implementation. It's optimal in size (4 numbers) and performance to compute most points/predicates/etc. you'd be interested in. – R.. GitHub STOP HELPING ICE May 18 '11 at 17:17

score 7 · Answer 2 · answered May 18 '11 at 16:09

Simple solution that works in N dimensions for convex polyhedra, of which a 2-dimensional rectangle is a special case:

Represent the polyhedron as the intersection of half-spaces, each defined by a unit normal vector and the distance of the surface hyperplane from the origin along the normal.
For each of these half-spaces, take the dot product of point in question with the defining normal vector. The point is in the half-space if and only if the dot product is less than [or equal to] the defining distance.
The point is inside the polyhedron if and only if it's in every one of the half-spaces.

For a rectangle defined as a counter-clockwise sequence of edges, step 1 amounts to rotating the edges each by 90 degrees clockwise to get the normals, then intersecting the normal line with the line containing the edge to find the distance to the origin.

Assuming step 1 is complete, testing a point takes at most 8 multiplications, 4 additions, and 4 comparisons.

If you want to, you can optimize the process a bit since you have rectangles (and thus opposite sides have opposite normals). Now you're only looking at 2 normals rather than 4, and a range of dot product values which indicate points that lie between the opposite sides. So now you're down to 4 multiplications, 2 additions, and 4 comparisons.

You can also get lucky if the first test you make shows that the point is outside the rectangle, in which case it's just 2 multiplications, 1 addition, and 1-2 comparisons.

Very elegant solution, though I did have to figure out what you meant by "half-spaces". — Jim Clay, May 18 '11 at 18:38
A halfspace is just the set of all `x` such that `x·v < c` for some fixed `v` and `c` (or `≤` if you prefer). — R.. GitHub STOP HELPING ICE, May 18 '11 at 19:15

score 3 · Answer 3 · answered May 18 '11 at 15:34

3

This is far from the best solution... But if you have the points in consecutive order, call them a, b, c, and d with an x and a y field, you can use the cross product of the vectors between your point p and each of the consecutive pairs.

If you always get the same sign for the result (i.e., all are positive or all are negative) then you're inside the rectangle; otherwise, you're outside.

answered May 18 '11 at 15:34

Platinum Azure

45,269
12
110
134

1

I believe this only works for convex quadrilaterals, but assuming it's a rectangle, then it's ok. Not a critique, though, just saying. – Chris A. May 18 '11 at 15:39
Can you give an examplee to support your answer...?? – AGeek May 18 '11 at 15:41
It will work for any convex polygon. – Platinum Azure May 18 '11 at 15:44
I'm actually thinking I might delete this answer-- I put a link in the question comments which I like better. – Platinum Azure May 18 '11 at 15:52
2

Interesting how the same questions come up at the same times of year -- AndreyT's answer you linked to is only about a week off from being exactly one year old! :-) – Jerry Coffin May 18 '11 at 16:10

groovingandi · Answer 4 · 2011-05-18T16:54:10.097

Define a new coordinate system with two rectangle sides as unit vectors and transform the coordinate of the point into the new coordinate system. If both coordinates are between 0 and 1, it's inside.

In equations (assuming A,B,C,D are corners of the rectangle, P is the point, _x and _y are the x and y components):

P_x = A_x + x * (B_x - A_x) + y * (D_x - A_x)
P_y = A_y + x * (B_y - A_y) + y * (D_y - A_y)

Solve for x and y and check if they are between 0 and 1

Written as linear equation system (A,B,C,D,P are vectors of length 2):

[    |    ]   [x]   [   ]
[B-A | D-A] * [ ] = [P-A]
[    |    ]   [y]   [   ]

Solving is easy as it has only two dimensions and you can be sure that you are not singular.

andand · Answer 5 · 2011-05-18T16:18:02.077

0

Since the rectangle could be rotated, you might want to consider an algorithm that is used to determine whether a point is interior to a convex polygon.

You could also compute the rotation angle of the rectangle, then transform both the rectangle and the point to axially align the rectangle. Then check to see if the transformed point is inside the axially aligned rectangle.

edited May 18 '11 at 16:18

answered May 18 '11 at 15:40

andand

17,134
11
53
79

"General polygon" is difficult and unnecessary. "General convex polygon" is what you want to consider. – R.. GitHub STOP HELPING ICE May 18 '11 at 15:57
@R.: Agreed. Answer updated. – andand May 18 '11 at 16:18

score 0 · Answer 6 · answered May 18 '11 at 15:56

You can rotate and move your reference system so it matches position and rotation of the rectangle. Now it is just a matter of simple comparisons between coordinates. This is more a mathematical way, so not the fastest (bellieve @Platinum Azure's one is)

score 0 · Answer 7 · answered May 18 '11 at 18:32

0

Finding whether a point lies within a bounded region like rectangle is part of the classic clipping algorithms. Refer to the wikipedia articles on Clipping and Line Clipping to know more about it.

answered May 18 '11 at 18:32

yasouser

5,113
2
27
41

Nikiton · Answer 8 · 2011-05-18T22:50:55.383

0

Following the spirit of @Jerry Coffin: create segments from rectangle corners to the point in question. Solve the linear equations. Slope is tan(a). Sum up all seq arctangents diff, if it is 2*PI and each diff < PI - point is inside the rectangle.

Edit Probably enough just check for each sequential difference < Pi...

edited May 18 '11 at 22:50

answered May 18 '11 at 21:50

Nikiton

268
1
7

how to determine whether a point lies inside a rectangle?

8 Answers8

Linked

Related