Перегляд вихідного коду сторінки Алгоритм Кіруса — Бека

'''Алгоритм Кіруса&nbsp;— Бека''' ({{lang-en|Cyrus — Beck}})&nbsp;— алгоритм [[Відсікання ліній|відсікання]] відрізків довільним [[опуклий многокутник|опуклим багатокутником]]. Був запропонований як ефективніша заміна [[Алгоритм Коена-Сазерленда|алгоритму Коена&nbsp;— Сазерленда]], який виконує відсікання за кілька ітерацій.<ref>{{Cite web |url=http://www.slideshare.net/johanna20/clipping-presentation |title=«Clipping» (презентація) |accessdate=14 червня 2016 |archive-date=4 березня 2016 |archive-url=https://web.archive.org/web/20160304054723/http://www.slideshare.net/johanna20/clipping-presentation }}</ref>

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

Відрізки, що відсікаються представляються в параметричному вигляді:
: <math>p(t) = p_0 + t(p_1-p_0), t \in [0, 1]</math>
де
: ''p<sub>0</sub>'', ''p<sub>1</sub>''&nbsp;— координати початку і кінця відрізка відповідно,
: ''t''&nbsp;— параметр.

Кожен відрізок, що відсікається, містить координати початку і кінця, а також два параметра ''t<sub>A</sub>'' та ''t<sub>B</sub>'', що відповідають початку і кінцю відрізка.
Для кожного відрізка, що відсікається ''P'' виконуються наступні дії:

* [[Ребро (геометрія)|Ребра]] багатокутника, що відсікає, обходяться [[проти годинникової стрілки]]. Для кожного ребра ''E'' обчислюється параметр ''t<sub>E</sub>'', що описує перетин ''E'' з прямою, на якій лежить відрізок ''P''. Обчислюється скалярний добуток вектора ''E'' та зовнішньої [[Нормаль (геометрія)|нормалі]] ''N'', в залежності від знака якого виникає одна з наступних ситуацій:
** ''E · N < 0''&nbsp;— відрізок ''P'' спрямований з внутрішньої на зовнішню сторону ребра ''E''. У цьому випадку параметр ''t<sub>A</sub>'' замінюється на ''t<sub>E</sub>'', якщо ''t<sub>E</sub>'' > ''t<sub>A</sub>''.
** ''E · N > 0''&nbsp;— відрізок ''P'' спрямований із зовнішньої на внутрішню сторону ребра ''E''. У цьому випадку параметр ''t<sub>B</sub>'' замінюється на ''t<sub>E</sub>'', якщо ''t<sub>E</sub>'' < ''t<sub>B</sub>''.
** ''E · N = 0''&nbsp;— відрізок ''P'' паралельний ребру ''E''. Відрізок ''P'' відкидається як невидимий, якщо знаходиться праворуч від ''E''.
* Якщо ''t<sub>A</sub>'' <math>\leq</math> ''t<sub>B</sub>'', то задана параметрами ''t<sub>A</sub>'' та ''t<sub>B</sub>'' частина відрізка ''P'' видима. В іншому випадку відрізок ''P'' повністю невидимий.

== Обчислювальна складність ==
{{ненаписаний розділ}}

== Див. також ==
* [[Алгоритм Ліанга–Барського]]
* {{не перекладено|Алгоритм Ніколла-Лі-Ніколла||en|Nicholl-Lee-Nicholl|}}

== Примітки ==
{{примітки}}

== Література ==
* Mike Cyrus, Jay Beck. «Generalized two- and three-dimensional clipping». Computers & Graphics, 1978: 23-28.
* James D. Foley. ''[http://books.google.com/books/about/Computer_graphics.html?id=-4ngT05gmAQC Computer graphics: principles and practice] {{Webarchive|url=https://web.archive.org/web/20160531145855/https://books.google.com/books/about/Computer_Graphics.html?id=-4ngT05gmAQC |date=31 травня 2016 }}''. 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

{{Algorithm-stub}}
{{rq|stub|refless}}
{{ВП-портали|Програмування|}}

[[Категорія:Геометричні алгоритми]]
[[Категорія:Алгоритми комп'ютерної графіки]]