Правило чет-нечет
Правило четности–нечетности — это алгоритм, реализованный в векторном графическом программном обеспечении, [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 : """Определяет, находится ли точка на пути, углу или границе многоугольника Args: x -- Координаты x точки. y -- Координаты y точки. poly -- список кортежей [(x, y), (x, y), ...] Возвращает: True, если точка находится на пути, является углом или находится на границе""" c = False for i in range ( len ( poly )): ax , ay = poly [ i ] bx , by = poly [ i - 1 ] if ( x == ax ) and ( y == ay ): # точка находится в углу return True if ( ay > y ) != ( by > y ): slope = ( x - ax ) * ( by - ay ) - ( bx - ax ) * ( y - ay ) if slope == 0 : # точка находится на границе return True if ( slope < 0 ) != ( by < ay ): c = not c return cСмотрите также
Ссылки
- ^ Дж. Д. Фоли, А. ван Дам, С. К. Фейнер и Дж. Ф. Хьюз. Компьютерная графика: принципы и практика. Серия «Системное программирование». Addison-Wesley, Reading, 2-е издание, 1990.
- ^ [1], w3c.org, получено 28.03.2019
- ^ "PNPOLY - Включение точек в тест полигонов - WR Franklin (WRF)".
Внешние ссылки
- Определение правил заполнения в SVG
 | Эта статья, связанная с программированием, является заглушкой . Вы можете помочь Википедии, расширив ее. |
