1. Mekansal shakllarning namoyishi. Ko'pburchak usuli

3. Segherland-Cohen algoritmi segmentni kesish usuli.

Amalda, grafik ob'ektlar har doim ekranning chegaralari yoki tashqi ekran tamponiga mos keladigan so'nggi rasterlarda ko'rsatiladi. Sonlu rasterdagi rasterizatsiya rasterli ob'ektga nisbatan raster chegaralariga nisbatan kesish imkoniyatini talab etadi, ya'ni. Rasterdan tashqaridagi rasterlashgan ob'ektning qismlarini o'chirish. Oldindan kesishsiz rasterlashtirish algoritmini ishga tushirish pikselning rangini rasterdan tashqarida koordinatalari bilan o'zgartirishga urinishda xato paydo bo'lishiga olib keladi (bu noto'g'ri pikseldagi rang o'zgarishini yoki hatto tizimning buzilishiga olib kelishi mumkin).
Eng oddiy kesish vazifasi segmentlarning kesmasi. Segerland-Koen algoritmi segmentni kesib o'tishga imkon beruvchi algoritmlardan biri hisoblanadi .
Sutherlend-Kohen algoritmi tekislikning to'rtburchak qismini tashkil etuvchi tekislik bilan 9 qismga bo'linadi. 9 qismdan har biri to'rt bitli kodga ega. Bits (eng kichikdan eng keksagacha) "chap", "o'ng", "past", "yuqoriroq" degan ma'noni anglatadi. Boshqacha qilib aytadigan bo'lsak, tekislikning chap tomonidagi samolyotning uchta qismi uchun eng kichik bit 1 va shunga o'xshash.

Kod qabul qilingandan so'ng, quyidagi variantlar mavjud:
1) Kodlar faqatgina 0dan iborat, ya'ni butun chiziq oynaning ichida joylashgan va butunlay chizilgan bo'lishi kerak;
2) Kodlar bir pozitsiyada bitta bitni o'z ichiga oladi, ya'ni segmentlar deraza tashqarisida joylashgan va chizilmaydi;
3) Boshqa barcha hollarda, segmentning faqat bir qismi oynada yotadi, bu esa kesish uchun zarurat borligini bildiradi.
Birinchi ikki holatda bitsel mantiqiy operatsiyalar bilan osongina tekshiriladi. Uchinchi narsa katta qiziqishdir. Keling, buni aniq bir misol bilan ko'rib chiqaylik.

Har ikki uchining kodi bitta bit bo'lsa, P1 yoki P2 oynaning tashqarisidan uning chegaralaridan biriga (yoki uning davomiga) harakat qiladi. Ya'ni. nuqta P1 R nuqtasiga, va P2 nuqtasini U nuqtasiga suradi. Yangi fikrlar uchun biz yana to'rt-bit kodlarni hisoblaymiz. Bizning holatda, segmentning uchlari hali ham derazadan tashqarida, ya'ni. biz yana bir harakatga muhtojmiz: R nuqtasi S nuqtasiga o'tadi va U nuqtasi T nuqtasiga o'tadi.
Chiqarish jarayoni yineluvchan bo'lib chiqadi. Har bir qadamda segmentning uchlari orasidagi masofa pasayadi, shuning uchun algoritm birlashishi mumkin. Natijada, segmentni (bizning holatda (S, T) ko'rsatiladi) ko'rsatiladi.
Keling, yana bir misolda bu algoritmning ishlashini ko'rib chiqamiz.

Segmentning joylashishi (P1; P2) to'liq ko'rinadigan shartlarga yoki to'liq ko'rinmaslik shartlariga mos kelmaydi, shuning uchun ham bu holatda, uzatish nuqtalarining ishlashiga murojaat qiladi.

O'tkazilgan tirnoqdan so'ng, yakuniy kodlar ikkinchi shartni qondiradi, ya'ni. Barcha segment ko'rsatilmaydi.
Shunday qilib, ushbu algoritm segmentning uchlari kodini belgilaydi. Agar har ikkala kod ham nol bo'lsa, segment butunlay to'rtburchakda. Agar bit va kodlar nol bo'lmasa, segment segmentning to'rtburchagini kesib o'tmaydi (bu segmentning har ikkala uchi to'rtburchakning bir tomonida) degan ma'noni anglatadi. Boshqa holatlarda algoritm nosfera kodini (ya'ni to'rtburchak tashqarisida) bo'lgan segmentni (yoki uchining bittasini) tanlaydi, segmentning eng yaqin kesishish nuqtasini to'rtburchakning yonlarini tashkil etuvchi to'g'ri chiziqlardan birida topadi va bu kesishish nuqtasini yangi oxir segment. Kesilgan segment yana algoritmdan o'tkaziladi.
Uch o'lchovli model uchun algoritmni amalga oshirish ikki o'lchovli dasturga o'xshaydi, faqat to'rt bitli kod o'rniga olti bit (chuqurlikning qo'shimcha ikki biti) ishlatiladi.