Is the point in the polygon random in shape?

Question

It is easy to determine if a point in a polygon is convex with the famous edge casting algorithm.

def point_inside_polygon(x, y, poly): """ Deciding if a point is inside (True, False otherwise) a polygon, where poly is a list of pairs (x,y) containing the polygon vertices. The algorithm is called the 'Ray Casting Method' """ n = len(poly) inside = False p1x, p1y = poly[0] for i in range(n): 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 

But what if the polygon is not completely convex?

How to determine if a point is in a randomly generated polygon defined by boundary points?

Say that I have a polygon of boundary points, for example,

How can i do this?

Best if in Python, but any general solutions are welcome.

Answer 1

Take out the ray and count how many times the ray crosses the polygon. (This can be annoying and error-prone if the edge lies exactly along the beam.) If it is an odd number, the point is in the polygon. Otherwise, it is not.

Answer 2

In fact, the ray casting method will work if you use the rule of nonzero winding number instead of the usual even odd rule .

This is explained in the Postscript Language Reference (where the word "path" means a list of polygonal vertices defining a polygon).

The rule with the number of the non-zero number of the winding determines whether a given point inside the path by conceptually drawing a ray from this point to infinity in any direction, and then studying the places where a segment of the path intersects the ray. Starting at 0, the rule adds 1 each time a path segment crosses a ray from left to right and subtracts 1 each time a segment crosses from right to left. After counting all the intersections, if the result is 0, then the point is out of the way; otherwise it is inside.