Русская Википедия:Правило чётный-нечётный
Правило чётного-нечётного — это алгоритм, реализованный в программном обеспечении для работы с векторной графикой (например, язык 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
См. также
Литература
развернутьПартнерские ресурсы |
---|