Алгоритм Кируса — Бека

Алгоритм Кируса — Бека (англ. Cyrus — Beck) — алгоритм отсечения отрезков произвольным выпуклым многоугольником. Был предложен в качестве более эффективной замены алгоритма Коэна — Сазерленда, который выполняет отсечение за несколько итераций.

Описание алгоритма

Отсекаемые отрезки представляются в параметрическом виде:

$p(t)=p_{0}+t(p_{1}-p_{0}),t\in [0,1]$

где

p₀, p₁ — координаты начала и конца отрезка соответственно,

t — параметр.

Каждый отсекаемый отрезок содержит координаты начала и конца, а также два параметра t_A и t_B, соответствующие началу и концу отрезка.
Для каждого отсекаемого отрезка P выполняются следующие действия:

• Рёбра отсекающего многоугольника обходятся против часовой стрелки. Для каждого ребра E вычисляется параметр t_E, описывающий пересечение E с прямой, на которой лежит отрезок P. Вычисляется скалярное произведение вектора P и внутренней нормали N ребра E, в зависимости от знака которого возникает одна из следующих ситуаций:
  • P · N < 0 — отрезок P направлен с внутренней на внешнюю сторону ребра E. В этом случае параметр t_A заменяется на t_E, если t_E > t_A.
  • P · N > 0 — отрезок P направлен с внешней на внутреннюю сторону ребра E. В этом случае параметр t_B заменяется на t_E, если t_E < t_B.
  • P · N = 0 — отрезок P параллелен ребру E. Отрезок P отбрасывается как невидимый, если находится по правую сторону от E.
• Если t_A $\leq$ t_B, то заданная параметрами t_A и t_B часть отрезка P видима. В противном случае отрезок P полностью невидим.

См. также

• Алгоритм Лианга — Барски
• Алгоритм Николла — Ли — Николла

Ссылки

• https://web.archive.org/web/20101203041134/http://cs1.bradley.edu/public/jcm/cs535CyrusBeck.html
• https://web.archive.org/web/20110725233122/http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm

Литература

• Mike Cyrus, Jay Beck. «Generalized two- and three-dimensional clipping». Computers & Graphics, 1978: 23-28.
• James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 117.