Правило чётного-нечётного — это алгоритм, реализованный в программном обеспечении для работы с векторной графикой (например, язык PostScript и масштабируемая векторная графика (SVG)), который определяет, как будет заполняться графическая фигура с более чем одним замкнутым контуром. В отличие от алгоритма с ненулевым правилом, этот алгоритм попеременно окрашивает и оставляет неокрашенными фигуры, определяемые вложенными замкнутыми контурами, независимо от их изгиба.
SVG определяет правило чётного-нечётного так:
Это правило определяет «внутренность» точки на холсте, проводя луч из этой точки в бесконечность в любом направлении и подсчитывая количество сегментов контура заданной фигуры, которые пересекает луч. Если это число нечётное, то точка находится внутри. Если — чётное, то точка снаружи.
Это правило в действии можно увидеть во многих программах для работы с векторной графикой (таких как Freehand или Illustrator), где пересечение контура с самим собой приводит к странному заполнению фигур.
На простой кривой правило четного-нечетного сводится к алгоритму решения задачи о принадлежности точки в многоугольнике.
Стандарт векторной компьютерной графики SVG может быть настроен на использование правила чётного-нечётного при рисовании многоугольников, хотя обычно он использует правило ненулевого индекса.
Реализация Ниже приведен пример реализации правила чётного-нечётного: def is_point_in_path(x: int, y: int, poly) -> bool: # Определить, находится ли точка внутри многоугольника.
# Аргументы: # x -- Координата x точки. # y -- Координата y точки. # poly -- список кортежей [(x, y), (x, y), ...]
# Возвращает: # True, если точка находится внутри контура, на угле или на границе. num = len(poly) j = num - 1 c = False for i in range(num): if (x == poly[i]) and (y == poly[i]): # точка является углом return True if (poly[i] > y) != (poly[j] > y): slope = (x - poly[i]) * (poly[j] - poly[i]) - (poly[j] - poly[i]) * (y - poly[i]) if slope == 0: # точка находится на границе return True if (slope < 0) != (poly[j] < poly[i]): c = not c j = i return c
См. также Правило ненулевого индекса
Литература
Категория:Алгоритмы компьютерной графики Категория:Незавершённые статьи о программировании