WikiSort.ru - Не сортированное

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

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

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

${\displaystyle 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. Вычисляется скалярное произведение вектора E и внешней нормали N, в зависимости от знака которого возникает одна из следующих ситуаций:
  • E · N < 0 — отрезок P направлен с внутренней на внешнюю сторону ребра E. В этом случае параметр t_A заменяется на t_E, если t_E > t_A.
  • E · N > 0 — отрезок P направлен с внешней на внутреннюю сторону ребра E. В этом случае параметр t_B заменяется на t_E, если t_E < t_B.
  • E · N = 0 — отрезок P параллелен ребру E. Отрезок P отбрасывается как невидимый, если находится по правую сторону от E.
• Если t_A ${\displaystyle \leq }$ t_B, то заданная параметрами t_A и t_B часть отрезка P видима. В противном случае отрезок P полностью невидим.

Вычислительная сложность

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 30 июня 2016 года.

См. также

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

Примечания

Ссылки

Имеется викиучебник по теме
«Алгоритм Кируса — Бека»

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

Для улучшения этой статьи желательно: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Проставив сноски, внести более точные указания на источники.