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

Правило чет-нечет — это алгоритм, реализованный в программном обеспечении для работы с векторной графикой. ^{[ 1 ]} например, язык PostScript и масштабируемая векторная графика (SVG), которая определяет, как будет заполняться графическая фигура с более чем одним замкнутым контуром. В отличие от алгоритма ненулевого правила , этот алгоритм альтернативно раскрашивает и оставляет неокрашенные фигуры, определенные вложенными замкнутыми путями, независимо от их витков.

SVG определяет правило четности-нечета следующим образом:

Это правило определяет «внутренность» точки на холсте, рисуя луч от этой точки до бесконечности в любом направлении и подсчитывая количество сегментов пути от заданной фигуры, которые пересекает луч. Если это число нечетное, точка находится внутри; если даже, то точка находится снаружи.

Это правило можно увидеть в действии во многих программах векторной графики (таких как Freehand или Illustrator ), где пересечение контура с самим собой приводит к странному заполнению фигур.

На простой кривой правило чета-нечета сводится к алгоритму решения проблемы точки в многоугольнике .

Стандарт компьютерной векторной графики SVG можно настроить на использование правила чет-нечет при рисовании многоугольников, хотя он использует ненулевое правило . по умолчанию ^{[ 2 ]}

Выполнение

Ниже приведен частичный пример реализации на Python . ^{[ 3 ]} используя луч справа от проверяемой точки:

def is_point_in_path(x: int, y: int, poly: list[tuple[int, int]]) -> bool:
    """Determine if the point is on the path, corner, or boundary of 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"""
    c = False
    for i in range(len(poly)):
        ax, ay = poly[i]
        bx, by = poly[i - 1]
        if (x == ax) and (y == ay):
            # point is a corner
            return True
        if (ay > y) != (by > y):
            slope = (x - ax) * (by - ay) - (bx - ax) * (y - ay)
            if slope == 0:
                # point is on boundary
                return True
            if (slope < 0) != (by < ay):
                c = not c
    return c

См. также

Ссылки

^ Дж. Д. Фоли, А. ван Дам, С. К. Фейнер и Дж. Ф. Хьюз. Компьютерная графика: принципы и практика. Системы Серия «Программирование». Аддисон-Уэсли, Ридинг, 2-е издание, 1990 г.
^ [1] , w3c.org, получено 28 марта 2019 г.
^ «PNPOLY — Включение точек в тест полигонов — WR Franklin (WRF)» .

Внешние ссылки

Определение правил заполнения в SVG

Эта компьютерному программированию, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[1] Дж. Д. Фоли, А. ван Дам, С. К. Фейнер и Дж. Ф. Хьюз. Компьютерная графика: принципы и практика. Системы Серия «Программирование». Аддисон-Уэсли, Ридинг, 2-е издание, 1990 г.

[2] [1] , w3c.org, получено 28 марта 2019 г.

[3] «PNPOLY — Включение точек в тест полигонов — WR Franklin (WRF)» .

[ 1 ]

[ 2 ]

[ 3 ]