Алгоритм Коена — Сазерленда

Алгоритм Коена — Сазерленда (англ. Cohen-Sutherland algorithm) — алгоритм відсікання відрізків, тобто алгоритм, який дозволяє визначити частину відрізка, яка перетинає прямокутник. Був розроблений Деном Коеном і Айвеном Сазерлендом у Гарварді в 1966–1968 рр., І опублікований на конференції AFIPS в 1968 .[1][2]

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

Алгоритм поділяє площину на 9 частин прямими, які утворюють сторони прямокутника. Кожній з 9 частин присвоюється чотирьохбітний код. Біти (від молодшого до старшого) означають «лівіше», «правіше», «нижче», «вище». Іншими словами, у тих трьох частин площини, які зліва від прямокутника, молодший біт дорівнює 1, і так далі.

Алгоритм визначає код кінців відрізка. Якщо обидва коди дорівнюють нулю, то відрізок повністю знаходиться в прямокутнику. Якщо бітове "І" кодів не дорівнює нулю, то відрізок не перетинає прямокутник (так як це означає, що обидві кінців відрізка знаходяться з однієї сторони прямокутника). В інших випадках, алгоритм вибирає кінець, що знаходиться поза прямокутником, знаходить найближчу до неї точку перетину відрізка з однієї з ліній, що утворює сторони прямокутника, і використовує цю точку перетину як новий кінець відрізка. Укорочений відрізок знову пропускається через алгоритм.

Реалізації


Примітки

  1. A Critical History of Computer Graphics and Animation. Section 4: Basic and applied research moves the industry (англ.).
  2. Robert F. Sproull, Ivan E. Sutherland A clipping divider // AFIPS Joint Computer Conferences: Proceedings of the December 9-11, 1968, fall joint computer conference. — New York: ACM, 1968. — Т. I. — С. 765–775.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.