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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Описание алгоритма[править | править вики-текст]

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

p(t) = p_0 + t(p_1-p_0), t \in [0, 1]

где

p0, p1 — координаты начала и конца отрезка соответственно,
t — параметр.

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

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

Вычислительная сложность[править | править вики-текст]

Реализация[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • 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.

См. также[править | править вики-текст]