Algoritmul Cohen-Sutherland

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Algoritmul Cohen-Sutherland este un algoritm de tăiere pentru segmente liniare care este utilizat pentru a determina dacă un segment sau o parte a acestuia trebuie afișat în zona de tăiere.

De exemplu, ne-am putea găsi într-o situație precum cea prezentată în figura 1.

Figura 1.

În această figură există trei segmente (1-2, 3-4, 5-6). Aceste segmente trebuie procesate diferit, deoarece segmentul 1-2 traversează întreaga zonă de tăiere (cea albastru închis) și trebuie „tăiat”, în timp ce segmentul 3-4, dimpotrivă, este complet în interior și, prin urmare, trebuie afișat integral.

Metodă

Prima fază a acestui algoritm implică calculul codului de ieșire , un cod de 4 biți , pentru fiecare punct extrem ( x , y ) al segmentului luat în considerare (deci pentru fiecare segment vom avea două coduri de ieșire ).

Imaginați-vă că liniile marginilor zonei de tăiere se extind până la infinit, ca în figura 2.

Figura 2. Extinderea marginilor zonei de tăiere

Cu această „extensie” putem identifica 9 zone (A, B, C, D, E, F, G, H, I), fiecare dintre ele fiind asociat cu un cod binar.

1001 1000 1010
0001 0000 0010
0101 0100 0110

Dacă punctul nostru ( x , y ) se încadrează într-una din aceste zone, codul de ieșire va fi cel relativ la aria sa. De exemplu, dacă punctul nostru aparține zonei F, codul său exterior va fi 0010.

Calculul codului de ieșire este destul de simplu: primii doi biți sunt determinați printr-o comparație a coordonatelor y , ceilalți doi printr-o comparație a coordonatelor x .

Pentru primii doi biți, luăm în considerare marginile superioare și inferioare ale zonei de tăiere ( Y min și Y max , amintiți-vă că în grafică originea este în partea stângă sus și valorile axei y cresc pe măsură ce merg în jos), ca în figura 3.

Figura 3.

Dacă y-ul nostru este mai mic decât Y min , atunci primul bit va fi setat la unu, altfel la zero. Dacă y-ul nostru este mai mare decât Y max , atunci al doilea bit va fi setat la unu, altfel la zero.

Aceeași procedură pentru ultimii doi biți, determinată de coordonatele x . În acest caz, luăm în considerare marginile din stânga și din dreapta zonei de tăiere ( X min și X max ), prezentate în figura 4.

Figura 4.

Dacă x-ul nostru este mai mare decât X max , atunci al treilea bit va fi setat la unu, altfel la zero. Dacă x-ul nostru este mai mic de X min , atunci al patrulea bit va fi setat la unu, altfel la zero.

La sfârșitul acestei proceduri, aplicată ambelor puncte extreme ale unui segment, am putea avea practic patru cazuri interesante:

  • ambele coduri de ieșire sunt egale cu 0000: acest lucru indică faptul că segmentul este complet în interiorul zonei de tăiere (segmentul 3-4 din figura 1 este un exemplu).
  • unul dintre cele două coduri de ieșire este egal cu 0000: înseamnă că o parte a segmentului trebuie scurtată (segmentul 5-6 din figura 1).
  • codurile de ieșire sunt identice (este suficient să le comparați cu o operație logică ȘI ): înseamnă că segmentul rămâne în aceeași zonă situată în afara zonei de tăiere. Segmentul va fi respins.
  • codurile de ieșire sunt diferite între ele și niciunul nu este egal cu 0000: în acest caz este necesar să se determine dacă segmentul intersectează de fapt zona de tăiere (de exemplu, prin calcularea punctului de intersecție, calcularea codului său exterior și verificarea faptului că acesta este sau nu 0000 ).
Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT