Determine if Point is in RectangleDate: 5/29/96 at 18:6:58 From: Mark Scott Subject: Determine if point is in rectangle I'm trying to find a formula that will allow me to determine whether a point specified lies within a polygon (rectangle - 4 points) or not. I'm not having much luck here! 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 Now if I want to see if a point given (say 2,18) lies inside of this shape... Well... that's my question. Help? Mark Scott Date: 5/31/96 at 15:33:45 From: Doctor Tom Subject: Re: 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 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 equation above, and just plug 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) let (50-10) f(x,y) = y - 10 - ------- (x - 1) (9-1) or, simplifying: f(x,y) = y - 10 - 5(x-1) or 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 into f(x,y). p3 = (51,40), and f(51,40) = 40 - 5 - 5*51 - a negative number. So every point (x,y) which makes f(x,y) negative will be on the "inside" of 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. 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. Here is another suggestion from a different doctor. 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. -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/