Точка литья лучей в полигоне для полигона с лучами, выровненными по краям

Я попытался использовать следующий код для Четно-нечетное правило из Википедии

# 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  |--------|

Обработка горизонтального края в качестве ребра делает обе точки, считающиеся внутри, при игнорировании горизонтального края заставляет обе точки рассматриваться как внешние

Итак, как я могу сделать работу четного порядка для такого полигона? Или предложить альтернативные алгоритмы?

Ответы

Ответ 1

Следующие правила, взятые из здесь, работают

Правила пересечения кромок

восходящий край включает в себя его начальную конечную точку и исключает ее конечную конечную точку;

нисходящий край исключает его начальную конечную точку и включает ее конечную конечную точку;

исключены горизонтальные ребра

точка пересечения лучей должна быть строго справа от точки P.

Обратите внимание, что приведенные выше правила соответствуют соглашению, которое

точка на левом или нижнем краю внутри, а точка на правом или верхнем краю находится снаружи. Таким образом, если два разных многоугольника имеют общий граничный сегмент, то точка на этом сегменте будет находиться в одном полигоне или другом, но не в обоих одновременно.

Также автор отмечает, что этот метод работает только для простых (несамопересекающихся) полигонов. Он также предлагает использовать эффективную реализацию чисел намотки, которая лучше обрабатывает непростые полигоны