Ненулевое правило
В двумерной компьютерной графике правило ненулевой обмотки является средством определения того, попадает ли заданная точка в замкнутую кривую. В отличие от похожего правила чет-нечет , оно опирается на знание направления штриха для каждой части кривой.
Для данной кривой C и данной точки P: постройте луч (прямую линию), исходящий из P в любом направлении к бесконечности. Найдите все пересечения C с этим лучом. Подсчитайте число оборотов следующим образом: для каждого пересечения по часовой стрелке (кривая, проходящая через луч слева направо, если смотреть из P) вычтите 1; для каждого пересечения против часовой стрелки (кривая, проходящая справа налево, если смотреть из P) прибавьте 1. Если общее число оборотов равно нулю, P находится снаружи C; в противном случае он находится внутри.
Число оборотов фактически является подсчетом того, сколько полных оборотов против часовой стрелки («витков») совершает кривая вокруг точки P, не замыкаясь на самой себе. (Если бы P был гвоздем, а C — свернутой петлей веревкой, попробуйте потянуть часть веревки в сторону от гвоздя: она либо освободится, либо окажется намотанной на гвоздь некоторое количество раз.)
В некоторых реализациях вместо этого подсчитывается количество оборотов по часовой стрелке, так что пересечения по часовой стрелке присуждаются +1, пересечения против часовой стрелки -1. Результат тот же.
Одно формальное определение числа оборотов точки P относительно кривой C (где P не лежит на кривой) выглядит следующим образом:
Рассмотрим точку Q, которая проходит один раз вокруг C. Конечная точка вектора от P до Q после нормализации проходит по единичной окружности с центром в P. Если мы представим себе траекторию этой конечной точки как резиновую ленту и позволим ленте сжиматься, то она в итоге обернется вокруг окружности некоторое количество раз. Число оборотов — это число оборотов (для оборотов по часовой стрелке число оборотов отрицательно). [1]
Стандарт векторной компьютерной графики SVG по умолчанию использует правило ненулевого значения при рисовании многоугольников. [2]
Смотрите также
Ссылки
- ^ Джеймс Д. Фоли, Андрис Ван Дам, Стивен К. Файнер и Джон Ф. Хьюз (1996) Компьютерная графика: принципы и практика стр. 965. Эддисон-Уэсли. ISBN 9780201848403
- ^ [1], w3c.org, получено 28 марта 2019 г.
Внешние ссылки
- Определение правил заполнения в SVG
- Объяснение Сонг Хо тесселятора OpenGL GLU
 | Эта статья, связанная с программированием, является заглушкой . Вы можете помочь Википедии, расширив ее. |
