У комп ютерній графіці відсікання відрізків це процес видалення відрізків або частин відрізків за межами оброблюваної ді

У комп'ютерній графіці, відсікання відрізків — це процес видалення відрізків або частин відрізків за межами оброблюваної ділянки. Як правило, будь-який відрізок або його частина, розташована за межами зони огляду, видаляється.

Є два загальних алгоритми для відсікання відрізків: Коена — Сазерленда і Ляна — Барського.

Метод відсікання відрізка складається з різних частин. Спочатку перевіряється, чи дана частина відрізка потрапляє в область видимості. Потім розраховуються перетини з однією (або декількома) межами відсікання.

Міститься частина відрізка всередині чи за межами області відсікання, визначається опрацюванням кінців відрізка перетину.

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

Докладніше: Алгоритм Коена — Сазерленда

Алгоритм Коена — Сазерленда (названий на честь ^[en] і Айвена Сазерленда) — це алгоритм відсікання відрізка. Алгоритм ділить двовимірний простір на 9 ділянок, з яких тільки середня ділянка (вікно перегляду) є видимою.

1967 року робота Дена Коена з моделювання польоту привела до розвитку алгоритмів відсікання відрізків для дво- і тривимірної комп'ютерної графіки, створених з Айваном Сазерлендом.

Алгоритм Ляна — Барського

Докладніше: Алгоритм Ляна — Барського

Алгоритм Ляна — Барського використовує параметричне рівняння відрізків і нерівності, що описують діапазон області відсікання для визначення перетину між відрізком і областю відсікання. За допомогою цих перетинів визначається, яку частину відрізка слід намалювати. Цей алгоритм є значно ефективнішим, ніж алгоритм Коена — Сазерленда, але другий швидше виконує тривіальні прийняття і відкидння, тому його варто використовувати тоді, коли більшість відрізків слід повністю вилучити.

Кірус — Бек

Докладніше: Алгоритм Кіруса — Бека

Дуже схожий на алгоритм відсікання відрізків Ляна — Барського. Різниця полягає в тому, що алгоритм Ляна — Барського є спрощеним різновидом алгоритму Кіруса — Бека, оптимізованим для прямокутного вікна відсікання.

Алгоритм Кіруса — Бека зі складністю O(N), в першу чергу призначений для відсікання відрізків у параметричній формі відносно опуклого многокутника в 2-х вимірах або відносно опуклого многогранника в 3-х вимірах.

Алгоритм Нікола — Лі — Нікола

Алгоритм Нікола — Лі — Нікола — це алгоритмом швидкого відсікання відрізків, що зменшує ймовірність відсікання одної частини відрізка кілька разів, як це може статися в алгоритмі Коена — Сазерленда. Вікно відсікання розділене на безліч різних областей, в залежності від положення початкової точки відрізка, яку потрібно відсікти.

Алгоритм O(lg N)

Цей алгоритм класифікує вершини за прямою, заданою в неявному вигляді р: ах + by + с = 0. Оскільки многокутник вважається опуклим і вершини впорядковано за годинниковою стрілкою або проти годинникової стрілки, то можна застосувати двійковий пошук, що приводить до часової складності O(lg N).

Швидке відсікання

Цей алгоритм схожий з алгоритмом Коена — Сазерленда. Розташування початку і кінця класифікуються за тим, у якій із 9 частин площини вони лежать. Оператор-перемикач спрямовує їх до відповідних обробників. На противагу, алгоритм Коена —Сазерленда, один і той самий випадок може оброблятися кілька разів.

Алгоритм Скали

Цей алгоритм заснований на однорідних координатах і двоїстості. Його можна використати для відсікання прямої або відрізків прямокутним вікном або опуклим многокутником. Алгоритм заснований на класифікації вершини вікна відсікання відносно півплощини, заданої прямою р: Ax + By + С = 0. Результат класифікації визначає ребра, які перетинає пряма р. Алгоритм простий, легко реалізується і розширюється на опуклі вікна. Пряму або відрізок р можна обчислити за точками x1, x2, заданих однорідними координатами безпосередньо, за допомогою векторного добутку:

p = x1 x x2 = [x1,y1,w1] x [x2,y2,w2] або

p = x1 x x2 = [x1,y1,1] x [x2,y2,1]

Див. також

Відсікання (комп'ютерна графіка)

Примітки

Renka, R. J. (19 жовтня 2014). (PDF). Department of Computer Science & Engineering, University of North Texas. Архів оригіналу (PDF) за 17 квітня 2016. Процитовано 10 травня 2017.
Cyrus, M., Beck, J.: Generalized Two and Three Dimensional Clipping, Computers&Graphics, Vol.3, No.1, pp.23-28, 1978
: O(lg N) Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol.18, No.4, 1994
Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459–467, 1987
Skala, V.: A new approach to line and line segment clipping in homogeneous coordinates, The Visual Computer, ISSN 0178-2789, Vol.21, No.11, pp.905-914, Springer Verlag, 2005

[1] Renka, R. J. (19 жовтня 2014). (PDF). Department of Computer Science & Engineering, University of North Texas. Архів оригіналу (PDF) за 17 квітня 2016. Процитовано 10 травня 2017.

[2] Cyrus, M., Beck, J.: Generalized Two and Three Dimensional Clipping, Computers&Graphics, Vol.3, No.1, pp.23-28, 1978

[3] : O(lg N) Line Clipping Algorithm in E2, Computers & Graphics, Pergamon Press, Vol.18, No.4, 1994

[4] Mark S. Sobkow, Paul Pospisil and Yee-Hong Yang. A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding//Computer & Graphics, Vol. 11, No. 4, pp. 459–467, 1987

[5] Skala, V.: A new approach to line and line segment clipping in homogeneous coordinates, The Visual Computer, ISSN 0178-2789, Vol.21, No.11, pp.905-914, Springer Verlag, 2005