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 tom-tom
def is_inside(polygon, point):
def det(p1, p2):
a, b = (p1[0] - point[0], p1[1] - point[1]), (p2[0] - point[0], p2[1] - point[1])
return a[0] * b[1] - a[1] * b[0]
def quadrant(p):
if p[0] > point[0] and p[1] >= p[1]:
return 0
if p[0] <= point[0] and p[1] > point[1]:
return 1
if p[0] < point[0] and p[1] <= point[1]:
return 2
if p[0] >= point[0] and p[1] < point[1]:
return 3
count = 0
for p1, p2 in zip(polygon, polygon[1:] + polygon[:1]):
q1, q2 = quadrant(p1), quadrant(p2)
if q1 is None or q2 is None:
#point in vertex
return True
q_diff = q2 - q1
if q_diff in (1, -3):
count += 1
elif q_diff in (-1, 3):
count -= 1
elif q_diff in (-2, 2):
d = det(p1, p2)
if d == 0:
#point on edge
return True
else:
count += 2 if d > 0 else -2
return count != 0
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"
Oct. 31, 2016
