Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
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.
"""
try:
return 0 != sum(raycast(p, a, b) for a, b in zip(poly, poly[1:]+(poly[0],)))
except EdgeException:
return True
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:
return 1
elif by <= py < ay and side_test(px, py, ax, ay, bx, by) < 0:
return -1
elif (ay == py == by and min(ax, bx) <= px <= max(ax, bx)) or a == p or b == p:
raise EdgeException
else:
return 0
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
return result
class EdgeException(Exception):
pass
April 7, 2015
