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

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

Опис алгоритму

Відрізки, що відсікаються представляються в параметричному вигляді:

${\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]

Примітки

1. . Архів оригіналу за 4 березня 2016. Процитовано 14 червня 2016.

Література

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

Посилання