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
_____________________________________________

Determine if Point is in Rectangle


Date: 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/   
    
Associated Topics:
High School Euclidean/Plane Geometry
High School Geometry
High School Triangles and Other Polygons

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/