how to determine whether a point lies inside a rectangle? [duplicate]

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.

Answer 1

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:

1. checking whether that X value is within the range of X values for the segment
2. if it is, plugging the X value into the equation of the line
3. 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).