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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

[ред. | ред. код]

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

де

p0, p1 — координати початку і кінця відрізка відповідно,
t — параметр.

Кожен відрізок, що відсікається, містить координати початку і кінця, а також два параметра tA та tB, що відповідають початку і кінцю відрізка. Для кожного відрізка, що відсікається P виконуються наступні дії:

  • Ребра багатокутника, що відсікає, обходяться проти годинникової стрілки. Для кожного ребра E обчислюється параметр tE, що описує перетин E з прямою, на якій лежить відрізок P. Обчислюється скалярний добуток вектора E та зовнішньої нормалі N, в залежності від знака якого виникає одна з наступних ситуацій:
    • E · N < 0 — відрізок P спрямований з внутрішньої на зовнішню сторону ребра E. У цьому випадку параметр tA замінюється на tE, якщо tE > tA.
    • E · N > 0 — відрізок P спрямований із зовнішньої на внутрішню сторону ребра E. У цьому випадку параметр tB замінюється на tE, якщо tE < tB.
    • E · N = 0 — відрізок P паралельний ребру E. Відрізок P відкидається як невидимий, якщо знаходиться праворуч від E.
  • Якщо tA tB, то задана параметрами tA та tB частина відрізка P видима. В іншому випадку відрізок P повністю невидимий.

Обчислювальна складність

[ред. | ред. код]

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. «Clipping» (презентація). Архів оригіналу за 4 березня 2016. Процитовано 14 червня 2016.

Література

[ред. | ред. код]

Посилання

[ред. | ред. код]