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
_____________________________________________

Determining If a Given Point Lies inside a Polygon

Date: 12/27/2005 at 05:55:30
From: Kapil
Subject: Point in polygon or not

I have a finite number of points that constitute a polygon, and a
point p(x,y).  I want to know if point p lies inside the polygon.



Date: 12/27/2005 at 10:29:16
From: Doctor Floor
Subject: Re: Point in polygon or not

Hi, Kapil,

Thanks for your question.  You will need to have formulas for the
sides, something like:

  y = 2x + 4

from starting point (1,6) to endpoint (3,10).

This is because points alone are not enough to define a polygon.  See 
for instance this polygon:

    +-------+
    |       |
    |       |
    |       |
    |   +   |
    |  / \  |
    | /   \ |
    |/     \|
    +       +


which has the same vertices as, but is a different polygon from:

    +-------+
     \      |
      \     |
       \    |
        +   |
       /    |
      /     |
     /      |
    +-------+


Provided that you have the formulae for the sides, make the formula 
for a line p(x,y) that does not pass through one of the vertices 
(points) of the polygon.  Intersect this line with all sides.  Count 
the number of intersections (only if they are between the starting
point and endpoint of the sides!) on the left hand side and right hand 
side of p.  If they are

  both even: p is outside of the polygon
  both odd: p is inside of the polygon

Do you see why this is true?

Examples:

        BOTH SIDES ODD

          \         /
          +\-------/-----------------+
          / \     /                 /
         /   \   /                 /
        /     \ /                 /
   ------------p----------------------
      /       / \               /
     /       /   \             /
    +-------/-----\-----------+
           /       \


        BOTH SIDES EVEN

                _.-'
           +_.-'---------------------+
        _.-'                        /
  \ _.-' /                         /
 --p------------------------------------------
    \  /                         /
     \/                         /
     /\                        /
    +--\----------------------+
        \

If you have more questions, just write back.

Best regards,

- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Triangles and Other Polygons
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/