У комп'ютерній графіці, відсікання відрізків — це процес видалення відрізків або частин відрізків за межами оброблюваної ділянки. Як правило, будь-який відрізок або його частина, розташована за межами зони огляду, видаляється.
Є два загальних алгоритми для відсікання відрізків: Коена — Сазерленда і Ляна — Барського.
Метод відсікання відрізка складається з різних частин. Спочатку перевіряється, чи дана частина відрізка потрапляє в область видимості. Потім розраховуються перетини з однією (або декількома) межами відсікання.
Міститься частина відрізка всередині чи за межами області відсікання, визначається опрацюванням кінців відрізка перетину.
Алгоритм Коена — Сазерленда
Алгоритм Коена — Сазерленда (названий на честь [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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U komp yuternij grafici vidsikannya vidrizkiv ce proces vidalennya vidrizkiv abo chastin vidrizkiv za mezhami obroblyuvanoyi dilyanki Yak pravilo bud yakij vidrizok abo jogo chastina roztashovana za mezhami zoni oglyadu vidalyayetsya Ye dva zagalnih algoritmi dlya vidsikannya vidrizkiv Koena Sazerlenda i Lyana Barskogo Metod vidsikannya vidrizka skladayetsya z riznih chastin Spochatku pereviryayetsya chi dana chastina vidrizka potraplyaye v oblast vidimosti Potim rozrahovuyutsya peretini z odniyeyu abo dekilkoma mezhami vidsikannya Mistitsya chastina vidrizka vseredini chi za mezhami oblasti vidsikannya viznachayetsya opracyuvannyam kinciv vidrizka peretinu Algoritm Koena SazerlendaDokladnishe Algoritm Koena Sazerlenda Algoritm Koena Sazerlenda nazvanij na chest en i Ajvena Sazerlenda ce algoritm vidsikannya vidrizka Algoritm dilit dvovimirnij prostir na 9 dilyanok z yakih tilki serednya dilyanka vikno pereglyadu ye vidimoyu 1967 roku robota Dena Koena z modelyuvannya polotu privela do rozvitku algoritmiv vidsikannya vidrizkiv dlya dvo i trivimirnoyi komp yuternoyi grafiki stvorenih z Ajvanom Sazerlendom Algoritm Lyana BarskogoDokladnishe Algoritm Lyana Barskogo Algoritm Lyana Barskogo vikoristovuye parametrichne rivnyannya vidrizkiv i nerivnosti sho opisuyut diapazon oblasti vidsikannya dlya viznachennya peretinu mizh vidrizkom i oblastyu vidsikannya Za dopomogoyu cih peretiniv viznachayetsya yaku chastinu vidrizka slid namalyuvati Cej algoritm ye znachno efektivnishim nizh algoritm Koena Sazerlenda ale drugij shvidshe vikonuye trivialni prijnyattya i vidkidnnya tomu jogo varto vikoristovuvati todi koli bilshist vidrizkiv slid povnistyu viluchiti Kirus BekDokladnishe Algoritm Kirusa Beka Duzhe shozhij na algoritm vidsikannya vidrizkiv Lyana Barskogo Riznicya polyagaye v tomu sho algoritm Lyana Barskogo ye sproshenim riznovidom algoritmu Kirusa Beka optimizovanim dlya pryamokutnogo vikna vidsikannya Algoritm Kirusa Beka zi skladnistyu O N v pershu chergu priznachenij dlya vidsikannya vidrizkiv u parametrichnij formi vidnosno opuklogo mnogokutnika v 2 h vimirah abo vidnosno opuklogo mnogogrannika v 3 h vimirah Algoritm Nikola Li NikolaAlgoritm Nikola Li Nikola ce algoritmom shvidkogo vidsikannya vidrizkiv sho zmenshuye jmovirnist vidsikannya odnoyi chastini vidrizka kilka raziv yak ce mozhe statisya v algoritmi Koena Sazerlenda Vikno vidsikannya rozdilene na bezlich riznih oblastej v zalezhnosti vid polozhennya pochatkovoyi tochki vidrizka yaku potribno vidsikti Algoritm O lg N Cej algoritm klasifikuye vershini za pryamoyu zadanoyu v neyavnomu viglyadi r ah by s 0 Oskilki mnogokutnik vvazhayetsya opuklim i vershini vporyadkovano za godinnikovoyu strilkoyu abo proti godinnikovoyi strilki to mozhna zastosuvati dvijkovij poshuk sho privodit do chasovoyi skladnosti O lg N Shvidke vidsikannyaCej algoritm shozhij z algoritmom Koena Sazerlenda Roztashuvannya pochatku i kincya klasifikuyutsya za tim u yakij iz 9 chastin ploshini voni lezhat Operator peremikach spryamovuye yih do vidpovidnih obrobnikiv Na protivagu algoritm Koena Sazerlenda odin i toj samij vipadok mozhe obroblyatisya kilka raziv Algoritm SkaliCej algoritm zasnovanij na odnoridnih koordinatah i dvoyistosti Jogo mozhna vikoristati dlya vidsikannya pryamoyi abo vidrizkiv pryamokutnim viknom abo opuklim mnogokutnikom Algoritm zasnovanij na klasifikaciyi vershini vikna vidsikannya vidnosno pivploshini zadanoyi pryamoyu r Ax By S 0 Rezultat klasifikaciyi viznachaye rebra yaki peretinaye pryama r Algoritm prostij legko realizuyetsya i rozshiryuyetsya na opukli vikna Pryamu abo vidrizok r mozhna obchisliti za tochkami x1 x2 zadanih odnoridnimi koordinatami bezposeredno za dopomogoyu vektornogo dobutku p x1 x x2 x1 y1 w1 x x2 y2 w2 abo p x1 x x2 x1 y1 1 x x2 y2 1 Div takozhVidsikannya komp yuterna grafika PrimitkiRenka R J 19 zhovtnya 2014 PDF Department of Computer Science amp Engineering University of North Texas Arhiv originalu PDF za 17 kvitnya 2016 Procitovano 10 travnya 2017 Cyrus M Beck J Generalized Two and Three Dimensional Clipping Computers amp Graphics Vol 3 No 1 pp 23 28 1978 O lg N Line Clipping Algorithm in E2 Computers amp 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 amp 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