Правило чётный-нечётный
Правило чётного-нечётного — это алгоритм, реализованный в программном обеспечении для работы с векторной графикой (например, язык PostScript и масштабируемая векторная графика (SVG)), который определяет, как будет заполняться графическая фигура с более чем одним замкнутым контуром. В отличие от алгоритма с ненулевым правилом, этот алгоритм будет попеременно окрашивать и оставлять неокрашенными фигуры, определяемые вложенными замкнутыми контурами, независимо от их изгиба.
SVG определяет правило чётного-нечётного так:
Это правило определяет «внутренность» точки на холсте, проводя луч из этой точки в бесконечность в любом направлении и подсчитывая количество сегментов контура заданной фигуры, которые пересекает луч. Если это число нечетное, то точка находится внутри. Если — четное, то точка снаружи.
Это правило в действии можно увидеть во многих программах для работы с векторной графикой (таких как Freehand или Illustrator), где пересечение контура с самим собой приводит к странному заполнению фигур.
На простой кривой правило четного-нечетного сводится к алгоритму решения задачи о принадлежности точки в многоугольнике.
Стандарт векторной компьютерной графики SVG может быть настроен на использование правила чётного-нечётного при рисовании многоугольников, хотя обычно он использует правило ненулевого индекса.
Реализация
Ниже приведен пример реализации правила чётного-нечётного: ётного-нечётного.
def is_point_in_path(x: int, y: int, poly) -> bool:
# Determine if the point is in the polygon.
#
# Args:
# x -- The x coordinates of point.
# y -- The y coordinates of point.
# poly -- a list of tuples [(x, y), (x, y), ...]
#
# Returns:
# True if the point is in the path or is a corner or on the boundary
num = len(poly)
j = num - 1
c = False
for i in range(num):
if (x == poly[i][0]) and (y == poly[i][1]):
# point is a corner
return True
if ((poly[i][1] > y) != (poly[j][1] > y)):
slope = (x-poly[i][0])*(poly[j][1]-poly[i][1])-(poly[j][0]-poly[i][0])*(y-poly[i][1])
if slope == 0:
# point is on boundary
return True
if (slope < 0) != (poly[j][1] < poly[i][1]):
c = not c
j = i
return c