Алгоритм Кируса — Бека () — алгоритм отсечения отрезков произвольным выпуклым многоугольником. Был предложен в качестве более эффективной замены алгоритма Коэна — Сазерленда, который выполняет отсечение за несколько итераций.
Описание алгоритма Отсекаемые отрезки представляются в параметрическом виде:
где p0, p1 — координаты начала и конца отрезка соответственно, t — параметр. Каждый отсекаемый отрезок содержит координаты начала и конца, а также два параметра tA и tB, соответствующие началу и концу отрезка. Для каждого отсекаемого отрезка P выполняются следующие действия: Рёбра отсекающего многоугольника обходятся против часовой стрелки. Для каждого ребра E вычисляется параметр tE, описывающий пересечение E с прямой, на которой лежит отрезок P. Вычисляется скалярное произведение вектора P и внутренней нормали N ребра E, в зависимости от знака которого возникает одна из следующих ситуаций: P · N < 0 — отрезок P направлен с внутренней на внешнюю сторону ребра E. В этом случае параметр tA заменяется на tE, если tE > tA. P · N > 0 — отрезок P направлен с внешней на внутреннюю сторону ребра E. В этом случае параметр tB заменяется на tE, если tE < tB. P · N = 0 — отрезок P параллелен ребру E. Отрезок P отбрасывается как невидимый, если находится по правую сторону от E. Если tA tB, то заданная параметрами tA и tB часть отрезка 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.
Категория:Геометрические алгоритмы