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/