Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Winding Number Algorithm solution in 3rd party category for Inside Block by sawako.oono
from typing import Tuple
import numpy as np
import math
def is_inside(polygon: Tuple[Tuple[int, int], ...], point: Tuple[int, int]) -> bool:
# Winding Number Algorithm
p0=np.array(point)
Theta=0
for i in range(len(polygon)):
p1=np.array(polygon[i])
p2=np.array(polygon[(i+1)%len(polygon)])
v1=p1-p0
v2=p2-p0
x=np.inner(v1,v2)
l1,l2=np.linalg.norm(v1),np.linalg.norm(v2)
if l1==0 or l2==0:#If point is on a vertice
return True
theta = np.arccos(x/(l1*l2))
if theta==math.pi:#If point is on a edge
return True
if np.cross(v1,v2)<0:
theta*=-1
Theta+=theta
if abs(Theta/math.pi)<0.00001: #If point is inside the polygoin abs(Theta) is 2pi else 0
return False
else:
return True
if __name__ == '__main__':
assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
(2, 2)) is True, "First"
assert is_inside(((1, 1), (1, 3), (3, 3), (3, 1)),
(4, 2)) is False, "Second"
assert is_inside(((1, 1), (4, 1), (2, 3)),
(3, 2)) is True, "Third"
assert is_inside(((1, 1), (4, 1), (1, 3)),
(3, 3)) is False, "Fourth"
assert is_inside(((2, 1), (4, 1), (5, 3), (3, 4), (1, 3)),
(4, 3)) is True, "Fifth"
assert is_inside(((2, 1), (4, 1), (3, 2), (3, 4), (1, 3)),
(4, 3)) is False, "Sixth"
assert is_inside(((1, 1), (3, 2), (5, 1), (4, 3), (5, 5), (3, 4), (1, 5), (2, 3)),
(3, 3)) is True, "Seventh"
assert is_inside(((1, 1), (1, 5), (5, 5), (5, 4), (2, 4), (2, 2), (5, 2), (5, 1)),
(4, 3)) is False, "Eighth"
print("All done! Let's check now")
June 29, 2021
