Правило чётный-нечётный

Правило чётного-нечётного — это алгоритм, реализованный в программном обеспечении для работы с векторной графикой (например, язык 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][0]) and (y == poly[i][1]):
            # точка является углом
            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:
                # точка находится на границе
                return True
            if (slope < 0) != (poly[j][1] < poly[i][1]):
                c = not c
        j = i
    return c

См. также править

Правило ненулевого индекса

Литература править

J. D. Foley, A. van Dam, S. K. Feiner, and J. F. Hughes. Computer Graphics: Principles and Practice. — 2nd edition. — Reading: Addison-Wesley, 1990. — (The Systems Programming Series).
Chopra Rajiv. Computer Graphics with An Introduction to Multimedia (англ.). — 4th Edition. — S CHAND & Company Limited, 2017. — ISBN 9789385676338.