Winding number solution in Clear category for Inside Block by Leonix
def is_inside(poly, p):
""" Plan is to count how many times a poly wraps around a point.
Zero times means that point is outside of a poly.
To count that we cast a ray directed at (1, 0) and see if it intersects
segments of a poly. A segment can intersect the ray upwards or downwards,
increasing or decreasing wrap count accordingly.
Wrap count can test for points strictly inside of a poly, but not on the edge.
However, we can still test for edge intersections with a clever exceptions use.
return 0 != sum(raycast(p, a, b) for a, b in zip(poly, poly[1:]+(poly,)))
def raycast(p, a, b):
""" 0 if segment (a, b) does not intersect the ray from p;
1 if intersects upwards;
-1 if intersects downwards;
raises EdgeException if p is exactly on the segment.
(px, py), (ax, ay), (bx, by) = p, a, b
if ay <= py < by and side_test(px, py, ax, ay, bx, by) > 0:
elif by <= py < ay and side_test(px, py, ax, ay, bx, by) < 0:
elif (ay == py == by and min(ax, bx) <= px <= max(ax, bx)) or a == p or b == p:
def side_test(px, py, ax, ay, bx, by):
# positive if (px,py) is on the left side of [(ax,ay), (bx,by)];
# negative if on the right side.
result = (bx-ax)*(py-ay) - (px-ax)*(by-ay)
if result == 0: raise EdgeException
April 7, 2015