Я попытался использовать следующий код для Четно-нечетное правило из Википедии
# x, y -- x and y coordinates of point
# poly -- a list of tuples [(x, y), (x, y), ...]
def isPointInPath(x, y, poly):
num = len(poly)
i = 0
j = num - 1
c = False
for i in range(num):
if ((poly[i][1] > y) != (poly[j][1] > y)) and \
(x < (poly[j][0] - poly[i][0]) * (y - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0]):
c = not c
j = i
return c
Несомненно, это дает неправильные результаты для моего простого прямолинейного многоугольника, когда моя контрольная точка выровнена с одним из горизонтальных ребер
-----
| |
| x ----|
x |--------|
Обработка горизонтального края в качестве ребра делает обе точки, считающиеся внутри, при игнорировании горизонтального края заставляет обе точки рассматриваться как внешние
Итак, как я могу сделать работу четного порядка для такого полигона? Или предложить альтернативные алгоритмы?