Алгоритм Кіруса — Бека — Вікіпедія

Алгоритм Кіруса — Бека (англ. 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 повністю невидимий.

Обчислювальна складність[ред. | ред. код]

Цей розділ статті ще не написаний Ви можете допомогти проекту, написавши цей розділ.

Див. також[ред. | ред. код]

• Алгоритм Ліанга–Барського
• Алгоритм Ніколла-Лі-Ніколла^[en]

Примітки[ред. | ред. код]

Література[ред. | ред. код]

• Mike Cyrus, Jay Beck. «Generalized two- and three-dimensional clipping». Computers & Graphics, 1978: 23-28.
• James D. Foley. Computer graphics: principles and practice [Архівовано 31 травня 2016 у Wayback Machine.]. Addison-Wesley Professional, 1996. p. 117.

Посилання[ред. | ред. код]

• 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

Це незавершена стаття про алгоритми. Ви можете допомогти проєкту, виправивши або дописавши її.

Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на сторінці обговорення. stubrefless