Skip to content

Instantly share code, notes, and snippets.

@alexander-ae
Created February 27, 2018 22:01
Show Gist options
  • Save alexander-ae/e3df947ce17cca7cd0324a4dcf66dd8d to your computer and use it in GitHub Desktop.
Save alexander-ae/e3df947ce17cca7cd0324a4dcf66dd8d to your computer and use it in GitHub Desktop.
Script para verificar si un punto pertenece a un polígono en base a https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
import sys
def punto_en_poligono(poly, p_x, p_y):
res = "Citizen"
count = 0
cantidad_de_vertices = len(poly)
p_x1, p_y1 = poly[0]
for i in range(cantidad_de_vertices):
p_x2, p_y2 = poly[(i + 1)]
ray = verifica_punto_en_linea(p_x, p_y, p_x1, p_y1, p_x2, p_y2)
if ray == "True":
count += 1
if ray == "Line":
res = "Prisoner"
break
p_x1, p_y1 = p_x2, p_y2
if count % 2 == 1:
res = "Prisoner"
return res
def verifica_punto_en_linea(p_cx, p_cy, x_1, y_1, x_2, y_2):
res = ""
if y_1 == y_2:
if p_cy == y_1:
if min(x_1, x_2) <= p_cx <= max(x_1, x_2):
res = "Line"
else:
res = "False"
if x_1 == x_2:
if p_cx == x_1:
if min(y_1, y_2) <= p_cy <= max(y_1, y_2):
res = "Line"
if res != "":
return res
if y_1 > y_2:
p_by = y_1
p_bx = x_1
p_ay = y_2
p_ax = x_2
else:
p_by = y_2
p_bx = x_2
p_ay = y_1
p_ax = x_1
if p_cy == p_ay or p_cy == p_by:
p_cy = p_cy + 0.1
if p_cy < p_ay or p_cy > p_by:
return "False"
elif p_cx >= max(p_ax, p_bx):
return "False"
else:
if p_cx < min(p_ax, p_bx):
return "True"
else:
if p_ax != p_bx:
m_1 = ((p_by - p_ay) * 1.0) / (p_bx - p_ax)
else:
res = "False"
if p_ax != p_cx:
m_2 = ((p_cy - p_ay) * 1.0) / (p_cx - p_ax)
else:
res = "True"
if m_2 >= m_1:
res = "True"
else:
res = "False"
return res
with open(sys.argv[1], 'r') as test_cases:
for test in test_cases:
line = test.strip()
parts = line.split(' | ')
coord_x = int((parts[1].split(' ')[0]))
coord_y = int((parts[1].split(' ')[1]))
polygon = [(int(point.split(' ')[0]),
int(point.split(' ')[1])) for point in parts[0].split(', ')]
print(punto_en_poligono(polygon, coord_x, coord_y))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment