To find a point inside a polygon

[Dan Schmidt]

David Yeung <dyeung at ust.hk> writes:

| Does anyone know if any python implementation for finding whether a
| point is inside a polygon? E.g., by giving a point(x,y) and an array
| of polygon's points (x0,y0,x1,y1,x2,y2,...), it returns true or
| false to tell if the given (x,y) is inside the polygon.

1) Draw a line from the point out to infinity.  The point is inside
   the polygon if it intersects an odd number of segments of the
   polygon.

2) (only works if the polygon is convex) Assuming the points go around
   the polygon counterclockwise, the point is in the polygon if it's
   to the left of (x0,y0)-(x1,y1), to the left of (x1,y1)-(x2,y2),
   etc.  Each of those tests is a simple operation involving a dot
   product or something.

-- 
Dan Schmidt | http://www.dfan.org