Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Inside Block by jtokaz
def is_inside(polygon, point):
# shift polygon so that point is origin
polygon = [(p[0]-point[0],p[1]-point[1]) for p in polygon]
cnt = 0 # count number of segments crossing positive x-axis
for i,p1 in enumerate(polygon):
p2 = polygon[(i+1)%len(polygon)]
if p2[1]*p1[1] <= 0: # crosses x axis, different y signs
if p1[1]==0==p2[1]: # both y-coords 0
if p1[0]>=0 or p2[0]>=0:
return True
else:
x_int = p2[0] - p2[1]*(p2[0]-p1[0])/(p2[1]-p1[1])
if x_int == 0:
return True
elif x_int > 0:
cnt = cnt + 1
for (u,v) in ((p1,p2),(p2,p1)):
if u[1] == 0 and u[0] >= 0 and u[1] > v[1]:
cnt = cnt + 1
return cnt%2==1
if __name__ == '__main__':
assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
(2, 2)) == True, "First"
assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
(4, 2)) == False, "Second"
assert is_inside(((1, 1), (4, 1), (2, 3)),
(3, 2)) == True, "Third"
assert is_inside(((1, 1), (4, 1), (1, 3)),
(3, 3)) == False, "Fourth"
assert is_inside(((2, 1), (4, 1), (5, 3), (3, 4), (1, 3)),
(4, 3)) == True, "Fifth"
assert is_inside(((2, 1), (4, 1), (3, 2), (3, 4), (1, 3)),
(4, 3)) == False, "Sixth"
assert is_inside(((1, 1), (3, 2), (5, 1), (4, 3), (5, 5), (3, 4), (1, 5), (2, 3)),
(3, 3)) == True, "Seventh"
assert is_inside(((1, 1), (1, 5), (5, 5), (5, 4), (2, 4), (2, 2), (5, 2), (5, 1)),
(4, 3)) == False, "Eighth"
June 28, 2015
