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

This question already has answers here: 开发者_JS百科 Closed 11 years ago.

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.

---

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

---

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

1. 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.
2. 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.
3. 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.

---

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.

---

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.

---

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)

---

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.

---

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.

---

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