Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Formula for Point in Rectangle


Date: 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/   
    
Associated Topics:
High School Equations, Graphs, Translations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/