Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Алгоритм Коена Сазерленда англ Cohen Sutherland algorithm алгоритм відсікання відрізків тобто алгоритм який дозволяє виз

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

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

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

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

image

Алгоритм поділяє площину на 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.

Посилання

  • Вільна реалізація[недоступне посилання з серпня 2019] на python
  • JavaScript polyline clipping library using Cohen-Sutherland algorithm [ 18 лютого 2017 у Wayback Machine.]
  • Delphi implementation [ 21 квітня 2017 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Algoritm Koena Sazerlenda angl Cohen Sutherland algorithm algoritm vidsikannya vidrizkiv tobto algoritm yakij dozvolyaye viznachiti chastinu vidrizka yaka peretinaye pryamokutnik Buv rozroblenij en i Ajvenom Sazerlendom u Garvardi v 1966 1968 rr I opublikovanij na konferenciyi AFIPS v 1968 Opis algoritmuAlgoritm podilyaye ploshinu na 9 chastin pryamimi yaki utvoryuyut storoni pryamokutnika Kozhnij z 9 chastin prisvoyuyetsya chotirohbitnij kod Biti vid molodshogo do starshogo oznachayut livishe pravishe nizhche vishe Inshimi slovami u tih troh chastin ploshini yaki zliva vid pryamokutnika molodshij bit dorivnyuye 1 i tak dali Algoritm viznachaye kod kinciv vidrizka Yaksho obidva kodi dorivnyuyut nulyu to vidrizok povnistyu znahoditsya v pryamokutniku Yaksho bitove I kodiv ne dorivnyuye nulyu to vidrizok ne peretinaye pryamokutnik tak yak ce oznachaye sho obidvi kinciv vidrizka znahodyatsya z odniyeyi storoni pryamokutnika V inshih vipadkah algoritm vibiraye kinec sho znahoditsya poza pryamokutnikom znahodit najblizhchu do neyi tochku peretinu vidrizka z odniyeyi z linij sho utvoryuye storoni pryamokutnika i vikoristovuye cyu tochku peretinu yak novij kinec vidrizka Ukorochenij vidrizok znovu propuskayetsya cherez algoritm RealizaciyiRealizaciya na movi S dlya dvovimirnoyi modeli define LEFT 1 dvijkove 0001 define RIGHT 2 dvijkove 0010 define BOT 4 dvijkove 0100 define TOP 8 dvijkove 1000 Tochka struct point double x y Pryamokutnik struct rect double x min y min x max y max Obchislennya kodu tochki r pokazhchik na struct rect p pokazhchik na struct point define vcode r p p gt x lt r gt x min LEFT 0 1 yaksho tochka livishe pryamokutnika p gt x gt r gt x max RIGHT 0 2 yaksho tochka pravishe pryamokutnika p gt y lt r gt y min BOT 0 4 yaksho tochka nizhche pryamokutnika p gt y gt r gt y max TOP 0 8 yaksho tochka vishe pryamokutnika yaksho vidrizok ab ne peretinaye pryamokutnik r funkciya povertaye 1 yaksho vidrizok ab peretinaye pryamokutnik r funkciya povertaye 0 i vidsikaye ti chastini vidrizka yaki znahodyatsya poza pryamokutnika int cohen sutherland const struct rect r struct point a struct point b int code a code b code kod kinciv vidrizka struct point c odna z tochok code a vcode r a code b vcode r b poki odna z tochok vidrizka poza pryamokutnikom while code a code b yaksho obidvi tochki z odnogo boku pryamokutnika to vidrizok ne peretinaye pryamokutnik if code a amp code b return 1 obirayemo tochku c z nenulovim kodom if code a code code a c a else code code b c b yaksho c livishe r todi peremishuyemo c na pryamu x r gt x min yaksho c pravishe r todi peremishuyemo c na pryamu x r gt x max if code amp LEFT c gt y a gt y b gt y r gt x min c gt x a gt x b gt x c gt x r gt x min else if code amp RIGHT c gt y a gt y b gt y r gt x max c gt x a gt x b gt x c gt x r gt x max yaksho c nizhche r todi peremishuyemo c na pryamu y r gt y min yaksho c vishe r to peremishuyemo c na pryamu y r gt y max else if code amp TOP c gt x a gt x b gt x r gt y min c gt y a gt y b gt y c gt y r gt y min else if code amp BOT c gt x a gt x b gt x r gt y max c gt y a gt y b gt y c gt y r gt y max onovlyuyemo kod if code code a a c code a vcode r a else b c code b vcode r b kodi rivni 0 otzhe obidvi tochki v pryamokutniku return 0 Realizaciya movoyu C dlya trivimirnoyi modeli define BOTTOM 1 00 000001 define LEFT 2 00 000010 define TOP 4 00 000100 define RIGHT 8 00 001000 define BACK 16 00 010000 define FRONT 32 00 100000 typedef struct Area float xlt ylt zlt Koordinati livogo verhnogo kuta blizhnoyi grani float xrb yrb zrb Koordinati pravogo nizhnogo kuta dalnoyi grani Area int GetCode const float point 1 4 const Area amp anArea int code 0 if point 0 1 gt anArea ylt Tochka vishe oblasti vidsikannya code TOP else if point 0 1 lt anArea yrb Tochka nizhche oblasti vidsikannya code BOTTOM if point 0 0 gt anArea xrb Tochka pravishe oblasti vidsikannya code RIGHT else if point 0 0 lt anArea xlt Tochka livishe oblasti vidsikannya code LEFT if point 0 2 lt anArea zlt Tochka pered oblastyu vidsikannya code FRONT else if point 0 2 gt anArea zrb Tochka za oblastyu vidsikannya code BACK return code Trivimirne vidsikannya metodom Koena Sazerlenda Beg koordinati pochatku vidrizka xn yn zn 1 End koordinati kincya vidrizka xk yk zk 1 AnArea koordinati oblasti yaka vidtinaye void CS Clip const float beg 1 4 const float end 1 4 const Area amp anArea Kodi kinciv vidrizka int outcode0 0 outcode1 0 outcodeOut 0 char codes 2 7 000000 000000 float temp 2 1 4 Prapor vidimosti i prapor zavershennya vidsikannya bool accept false done false outcode0 GetCode beg codes 0 anArea Obchislyuyemo pochatkovi kodi kinciv vidrizka outcode1 GetCode end codes 1 anArea do float x y z if outcode0 outcode1 Vidrizok povnistyu vidimij accept true done true else if outcode0 amp outcode1 Vidrizok povnistyu nevidimij done true else Vidrizok chastkovo vidimij Obchislennya tochok peretinu vidrizka ta oblasti vidsikannya outcodeOut outcode0 outcode0 outcode1 if outcodeOut amp TOP x beg 0 0 end 0 0 beg 0 0 anArea ylt beg 0 1 end 0 1 beg 0 1 z beg 0 2 end 0 2 beg 0 2 anArea ylt beg 0 1 end 0 1 beg 0 1 y anArea ylt else if outcodeOut amp BOTTOM x beg 0 0 end 0 0 beg 0 0 anArea yrb beg 0 1 end 0 1 beg 0 1 z beg 0 2 end 0 2 beg 0 2 anArea yrb beg 0 1 end 0 1 beg 0 1 y anArea yrb else if outcodeOut amp RIGHT y beg 0 1 end 0 1 beg 0 1 anArea xrb beg 0 0 end 0 0 beg 0 0 z beg 0 2 end 0 2 beg 0 2 anArea xrb beg 0 0 end 0 0 beg 0 0 x anArea xrb else if outcodeOut amp LEFT y beg 0 1 end 0 1 beg 0 1 anArea xlt beg 0 0 end 0 0 beg 0 0 z beg 0 2 end 0 2 beg 0 2 anArea xlt beg 0 0 end 0 0 beg 0 0 x anArea xlt else if outcodeOut amp FRONT x beg 0 0 end 0 0 beg 0 0 anArea zlt beg 0 2 end 0 2 beg 0 2 y beg 0 1 end 0 1 beg 0 1 anArea zlt beg 0 2 end 0 2 beg 0 2 z anArea zrb else if outcodeOut amp BACK x beg 0 0 end 0 0 beg 0 0 anArea zrb beg 0 2 end 0 2 beg 0 2 y beg 0 1 end 0 1 beg 0 1 anArea zrb beg 0 2 end 0 2 beg 0 2 z anArea zlt if outcodeOut outcode0 temp 0 0 0 x temp 0 0 1 y temp 0 0 2 z outcode0 GetCode temp 0 codes 0 anArea else temp 1 0 0 x temp 1 0 1 y temp 1 0 2 z outcode1 GetCode temp 1 codes 1 anArea while done if accept Vidrizok povnistyu vidimij Vidrizok na ekran LINE temp 0 temp 1 PrimitkiA Critical History of Computer Graphics and Animation Section 4 Basic and applied research moves the industry angl 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 T I S 765 775 PosilannyaVilna realizaciya nedostupne posilannya z serpnya 2019 na python JavaScript polyline clipping library using Cohen Sutherland algorithm 18 lyutogo 2017 u Wayback Machine Delphi implementation 21 kvitnya 2017 u Wayback Machine

Дата публікації:
Топ