Python Point in Polygon Test

This function will test if a point (x,y) lies within a polygon (x,y),(x,y),(x,y).

I did not invent this code - it comes from a well known algorithm called the "Ray Casting Method". The basic principle is a ray cast from INSIDE a polygon will cross an ODD number of boundaries. A ray cast from OUTSIDE a polygon will cross an EVEN number of boundaries. It really works and is a very clever algorithm. The following image summarizes the mechanics:

Code:

# Determine if a point is inside a given polygon or not
# Polygon is a list of (x,y) pairs. This fuction
# returns True or False. The algorithm is called
# "Ray Casting Method".

def point_in_poly(x,y,poly):

   n = len(poly)
   inside = False

   p1x,p1y = poly[0]
   for i in range(n+1):
   p2x,p2y = poly[i % n]
   if y > min(p1y,p2y):
   if y <= max(p1y,p2y):
   if x <= max(p1x,p2x):
   if p1y != p2y:
   xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
   if p1x == p2x or x <= xinters:
   inside = not inside
   p1x,p1y = p2x,p2y

   return inside

## Test

polygon = [(0,10),(10,10),(10,0),(0,0)]

point_x = 5
point_y = 5

## Call the fuction with the points and the polygon
print point_in_poly(point_x,point_y,polygon)

Reference: http://www.ariel.com.au/a/python-point-int-poly.html