Formula for Point in RectangleDate: 5/29/96 at 18:6:58 From: Anonymous Subject: How to Determine if Point is in Rectangle Hi, I'm trying to find a formula that will allow me to determine whether or not a specified point lies within a polygon (rectangle - 4 points). The problem is that the shape is not perpendicular to the X-Y plane. That is to say, it's tilted slightly to the right and down. Here's an example starting with the lower left corner of the shape: p1 = 1,10 p2 = 9,50 p3 = 51,40 p4 = 36,1 How can I see if a given point (2,18) lies inside this shape? Mark Scot Date: Friday, May 31, 1996 10:33 AM From: Dr. Tom Subject: How to Determine if Point is in Rectangle This is a very standard problem in computer graphics, and here is the general approach that will work not only for a rectangle, but for any convex polygon. I assume that the points p1, p2, p3, and p4 are placed in order around the rectangle - in other words, if I put my pencil on p1, then drag it to p2, p3, p4, and back to p1 with straight lines, I'll draw the outline of the rectangle and not some bow-tie-like thing. I assume further that you're familiar with the equation of a line connecting two points (x1,y1) and (x2,y2): (y2 - y1) 0 = y - y1 - --------- (x - x1) (x2 - x1) (This may look a little funny, but I just wrote the usual equation down and moved everything to one side, leaving zero on the other.) Now here's something you may not have thought about: If you forget about the zero on the left side of the above equation, and just plug in numbers for x and y into the formula on the right side, the result will be zero exactly when a point with coordinates (x,y) is on the line. If (x,y) is not on the line, the result will not be zero. In fact, every point (x,y) on one side of the line will give negative values in the formula, and every (x,y) on the other side of the line will give positive values. So you just need to figure out which is which. To test if a given point is in the rectangle, it has to be on the correct side of each of the four lines. Let's use your example, and I'll show you how to see if a point (x,y) is on the "correct side" of the line connecting p1 and p2. p1 = (1,10) and p2 = (9, 50) (50-10) let f(x,y) = y - 10 - ------- (x - 1) (9-1) or, simplifying: f(x,y) = y - 10 - 5(x-1) f(x,y) = y - 5 - 5x. You can check this: If x=1 and y=10, f(x,y) = 0. Similarly, if x=9 and y=50, f(x,y) = 0. Now the inside of the rectangle is on the same side as either p3 or p4 (you can use either). So let's put the coordinates of p3 = (51,40) into f(x,y): f(51,40) = 40 - 5 - 5*51 which is a negative number. So every point (x,y) which makes f(x,y) negative will be on the "inside" of a line connecting p1 and p2. To be sure your point is inside all four lines, you have to do a similar check on each of the other three points. This may seem ugly, but it works not only for any rectangle, but also for any convex polygon. Another option is to rotate the coordinates so that a pair of lines is parallel to the x-axis, and to test an arbitrary point, apply the same rotation to it, and then the inside/outside tests are the obvious ones for coordinate-aligned rectangles. If you know how to construct a rotation matrix like this, it's probably a slightly faster solution, but note that it will only work for rectangles, while my method above is much more general, and requires nothing more than elementary algebra to solve. I hope this helps. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Here is another suggestion from a different doctor: I just wanted to suggest another way for rectangles. Let vk=Pk-P4 for k=1,2,3. Figure out which two vk are perpendicular by seeing which vk dot vj = 0. Say it's v1 and v2, so v3=v1+v2. p is in the rectangle if and only if both (p,v1)/(v1,v1) and (p,v2)/(v2,v2) are between 0 and 1, i.e. coordinates of p with respect to the orthogonal basis v1 and v2. Date: 5/31/96 at 17:44:53 From: Mark Scott Subject: How to Determine if Point is in Rectangle Thanks so much. Here's what the function looks like in Visual Basic: While i < numpoints If ((((ppy(i) <= pnty) And (pnty < ppy(j))) Or ((ppy(j) <= pnty) And (pnty < ppy(i)))) And _ (pntx < (ppx(j) - ppx(i)) * (pnty - ppy(i)) / (ppy(j) - ppy(i)) + ppx(i))) Then InFlag = Not InFlag End If j = i i = i + 1 Wend ppx and ppy are in an array of points where (j) is 1 minus (i) and pntx and pnty are the x and y values passed to it - the point I'm evaluating. Thanks again! It works like a champ... Date: 6/3/96 at 10:32:21 From: Doctor Tom Subject: How to Determine if Point is in Rectangle Hi Mark, Of course, last night on my way home, a "better" way to solve your problem occurred to me. Now that you've got it working, of course, there's no reason to change, but I thought I'd tell you the better way as well. Given any three points on the plane (x0,y0), (x1,y1), and (x2,y2), the area of the triangle determined by them is given by the following formula: 1 | x0 y0 1 | A = - | x1 y1 1 |, 2 | x2 y2 1 | where the vertical bars represent the determinant. If you don't know what a determinant is, it doesn't matter too much; the value of the expression above is: (.5)(x1*y2 - y1*x2 -x0*y2 + y0*x2 + x0*y1 - y0*x1) The amazing thing is that A is positive if the three points are taken in a counter-clockwise orientation, and negative otherwise. To be inside a rectangle (or any convex body), as you trace around in a clockwise direction from p1 to p2 to p3 to p4 and back to p1, the "areas" of triangles p1 p2 p, p2 p3 p, p3 p4 p, and p4 p1 p must all be positive. If you don't know the orientation of your rectangle, then they must either all be positive or all be negative. I think the calculation this way is perhaps even a little cleaner. And again, this method works for arbitrary convex regions on the plane. -Doctor Tom, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/