Elemi grafikai algoritmusok

Megjegyzés: minden algoritmusnál normál koordináta-rendszert tételezünk fel, ezért a 'Rajzol' eljárásnak kell még gondoskodnia a képre transzformálásról.

1. szakasz rajzolás

A: egyszerű algoritmus

A szakasz végpontjai legyenek (X1,Y1), illetve (X2,Y2)! Tegyük fel, hogy X2>X1! A két ponton át húzható egyenes egyenlete ekkor: Y=(X-X1)/(X2-X1)*(Y2-Y1)+Y1

Rajzolás:
  SZ:=(Y2-Y1)/(X2-X1)                  [X1=X2 esetén]
  Ciklus X=X1-től X2-ig
    Y:=(X-X1)*SZ+Y1
    Rajzol(X,Y)
  Ciklus vége
Eljárás vége.

Ekkor az az alapvető probléma, hogy ha Y2-Y1 nagyobb, mint X2-X1, akkor a vonal nem lesz folytonos.

B: folytonos vonallal

Rajzolás:
  HX:=X2-X1: HY:=Y2-Y1
  Ha abs(HX)>abs(HY) akkor H:=abs(HX) különben H:=abs(HY)
  Ha H=0 akkor
          Rajzol(X1,Y1)
      különben
          LX:=HX/H: LY:=HY/H
          X:=X1: Y:=Y1
          Ciklus K=1-től H+1-ig
           Rajzol(X,Y)
           X:=X+LX : Y:=Y+LY
          Ciklus vége
  Elágazás vége
Eljárás vége.

2. kör rajzolás

Mielőtt a kör rajzolást elkezdenénk, egy egyszerű észrevételt tehetünk: Ha egy origó középpontú kört rajzolunk, akkor abból, hogy az (x,y) pont pontja a körvonalnak, követ­kezik, hogy az (x,-y), a (-x,y) és a (-x,-y) is az, hiszen a kör egy szimmetrikus alakzat.

A: a körvonal pontjai: x,sqr(r*r-x*x)

Egy origó középpontú, r sugarú kör pontjaira a következő azonosság igaz: x*x+y*y=r*r! Ezt felhasználva készíthetjük el az első megoldást!

Rajzolás:
  Ciklus X=0-tól R-ig
    Y:=gyök(R*R-X*X)
    Rajzol(X,Y): Rajzol(X,-Y)
  Rajzol(-X,Y): Rajzol(-X,-Y)
  Ciklus vége
Eljárás vége.

B: a körvonal pontjai: r*cos(alfa),r*sin(alfa)

A körvonal azon pontjának koordinátái, amely az x-tengellyel alfa szöget zár be, a kö­vetkező azonossággal számolhatók:  x=r*cos(alfa), y=r*sin(alfa)

Rajzolás:
  Ciklus ALFA=0-tól pi/2-ig .01-esével
    X:=R*cos(ALFA): Y:=R*sin(ALFA)
    Rajzol(X,Y): Rajzol(X,-Y)
    Rajzol(-X,Y): Rajzol(-X,-Y)
  Ciklus vége
Eljárás vége.

A megoldás problémája olyan lépésköz meghatározása, amelynél a körvonal még összefüggő, de nem kell túl sok pontot rajzolni (elég gyors a megoldás). A negyedkör kerülete r*pi/2, így akkor érnek össze a körvonal pontjai, ha a lépésköz 1/r.

C: a körvonal pontjai: x,sqr((x+r)*(r-x))

Ha a kör átmérőjének két végpontját összekötjük a körvonal egy tetszőleges pontjával, akkor egy derékszögű háromszöget kapunk. Ennek a derékszögű háromszögnek a magassága adja meg az x koordinátához az y koordinátát. A derékszögű há­romszög magasságára az alábbi ábra alapján a következő kép­let adható: y*y=(r+x)*(r-x)

Rajzolás:
  Ciklus X=0-tól R-ig
    Y:=gyök((R+X)*(R-X))
    Rajzol(X,Y): Rajzol(X,-Y): Rajzol(-X,Y): Rajzol(-X,-Y)
  Ciklus vége
Eljárás vége.

Mindhárom megoldás esetén az az alapvető probléma, hogy nem biztos, hogy a kör­vonal folytonos vonal lesz, illetve elképzelhető, hogy nagyon sok pontot rajzolunk egy­másra.

D: folytonos vonallal

Ebben a megoldásban kiindulunk abból, hogy a (0,r) pont pontja a körvonalnak. Ha az I. síknegyedbe eső körvonalat rajzoljuk, akkor egy tetszőleges körvonalra eső pont után a következő pont vagy tőle jobbra található, vagy jobbra és lefele, vagy pedig lefele. Pró­báljuk ki –ilyen sorrendben–, hogy melyik nem lép ki a körvonalon kívülre!

Rajzolás:
  X:=0: Y:=R: RR:=R*R
  Ciklus amíg Y0
    Rajzol(X,Y): Rajzol(X,-Y): Rajzol(-X,Y): Rajzol(-X,-Y)
    Ha (X+1)*(X+1)+Y*YRR akkor X:=X+1
    különben Y:=Y-1
             Ha (X+1)*(X+1)+Y*YRR akkor X:=X+1
             [különben le]
    Elágazások vége
  Ciklus vége
Eljárás vége.

Megjegyzés: Ez az algoritmus használható tetszőleges konvex alakzat rajzolásához is.

E: A körvonal követésével

Körvonalpont(x,y):
  Rajzol(x,y): Rajzol(-x,y): Rajzol(-x,-y ): Rajzol(x,-y )
  Rajzol(y,x ): Rajzol(-y,x ): Rajzol(-y,-x ): Rajzol(y,-x)
Eljárás vége.

Körrajz(r):
  x:=0: y:=r [a tetején kezdjük, Kelet felé egy nyolcadot]
  d:=1-r: dE:=3: dSE:=-2*r+5
  Körvonalpont(x,y)
  Ciklus amíg y>x
    Ha d<0 akkor  [Keletre lépés]
      d:=d+dE: dE:=dE+2: dSE:=dSE+2
      x:=x+1               [ y:=y ]
    különben   [Délkeletre lépés]
      d:=d+dSE: dE:=dE+2: dSE:=dSE+4
      x:=x+1: y:=y-1
      Körvonalpont(x,y)
  Ciklus vége
Eljárás vége.

3. Pont rajzoló eljárás

Tegyük fel, hogy a képernyő sorainak számát az SS, oszlopainak számát az OS változó tartalmazza, a képernyő origója a bal felső sarokban van,a koordináták jobbra, illetve lefelé növekszenek. Legyen a valódi koordinátatengely origója a képernyő KS. sor KO. oszlopában és irányitása legyen a szokásos! A rajzoló eljárás a paraméterként kapott valós koordináta értékeket kerekítse egészre, s a pontot csak akkor ábrázolja, ha a képernyőn van. Ebben a megoldásban a valós koordinátarendszer és a képernyő­koordinátarendszer léptéke azonos. (Ha nem azonos lenne, akkor X-et és Y-t meg kell szorozni a megfelelő léptékkel.)

Rajzol(X,Y):
  S:=Kerekít(KS-Y): O:=Kerekít(KO+X)
  Ha S0 és S<SS és O0 és O<OS akkor Pontrajzolás(O,S)
Eljárás vége.

4. Alakzatok színezése:

A. Rekurzív festés pontonként

Ez az eljárás egy belső pontból kiindulva festi be az alakzatot. A rekurzió miatt nagy alakzatokhoz túl nagy a memóriaigénye.

Festés(X,Y):
  Pontrajzolás(X,Y)
  Ha üres(X-1,Y) akkor Festés(X-1,Y)
  Ha üres(X,Y-1) akkor Festés(X,Y-1)
  Ha üres(X+1,Y) akkor Festés(X+1,Y)
  Ha üres(X,Y+1) akkor Festés(X,Y+1)
Eljárás vége.

B. Sort alkalmazó festés pontonként

Ez az eljárás az előző egy gazdaságosabb változata, egy hullámfrontot ábrázol sor adatszerkezetben..

Festés(X,Y):
  Pontrajzolás(X,Y): Sorba(X,Y)
  Ciklus amíg a sor nem üres
    Sorból(X,Y)
    Ha üres(X-1,Y) akkor Pontrajzolás(X-1,Y): Sorba(X-1,Y)
    Ha üres(X,Y-1) akkor Pontrajzolás(X,Y-1): Sorba(X,Y-1)
    Ha üres(X+1,Y) akkor Pontrajzolás(X+1,Y): Sorba(X+1,Y)
    Ha üres(X,Y+1) akkor Pontrajzolás(X,Y+1): Sorba(X,Y+1)
  Ciklus vége
Eljárás vége.

D. Vermet alkalmazó festés pontonként

Ez az eljárás az előző egy másik változata, vermet használ a még feldolgozandó belső pontok ábrázolására.

Festés(X,Y):
  Pontrajzolás(X,Y): Verembe(X,Y)
  Ciklus amíg a verem nem üres
    Veremböl(X,Y)
    Ha üres(X-1,Y) akkor Pontrajzolás(X-1,Y): Verembe(X-1,Y)
    Ha üres(X,Y-1) akkor Pontrajzolás(X,Y-1): Verembe(X,Y-1)
    Ha üres(X+1,Y) akkor Pontrajzolás(X+1,Y): Verembe(X+1,Y)
    Ha üres(X,Y+1) akkor Pontrajzolás(X,Y+1): Verembe(X,Y+1)
  Ciklus vége
Eljárás vége.

E. Háromszögfestés

Egy háromszöget könnyű festeni, ha megadjuk azokat a vízszintes szakaszokat, ame­lyekkel teljesen befesthető. Ezen szakaszok végpontjai az oldalegyenesek egyenleteiből számolhatók, azaz nincs szükség a képmemória leolvasására.

Háromszögfestés(A,B,C):
  Ciklus S=C.Y-tól A.Y-ig
    O1:=(A-C egyenes) az S. sorban
    O2:=(B-C egyenes) az S. sorban
    Vonal(O1,S,O2,S)
  Ciklus vége
  Ciklus S=A.Y+1-től B.Y-ig
    O1:=(A-B egyenes) az S. sorban
    O2:=(B-C egyenes) az S. sorban
    Vonal(O1,S,O2,S)
  Ciklus vége
Eljárás vége.

F. Rekurzív festés szakaszonként

Egy alakzat kiszínezéséhez meg kell adni egy belső pontját. Ekkora színezést a kö­vetkezőképpen végezzük el. Húzzuk meg azt a függőleges vonalat, amely ezen a pon­ton keresztül halad, s a kiszínezendő ábra legközelebbi határvonaláig tart. Ez a vonal a kiszínezendő ábrát (legalább) 2 részre vágja: a vonaltól balra, illetve jobbra levő részre. (Kettőnél több részről akkor van szó, ha a vonal érintette valahol a kiszínezendő áb­rát.) A feladat ezek után e két rész kiszínezése. Ezt úgy oldjuk meg, hogy végigme­gyünk a vonal mindkét oldalán, s ha belső, még kiszínezetlen pontot találunk, akkor a fenti eljárás végrehajtjuk ebből a pontból kiindulva.

Festés(X,Y):
  Vonalvég(-1,X,Y,Y1): Vonalvég(1,X,Y,Y2)
  Vonalrajzolás(X,Y1,X,Y2)
  Ciklus I=Y1-től Y2-ig
    Ha üres(X-1,I) akkor Festés(X-1,I)
    Ha üres(X+1,I) akkor Festés(X+1,I)
  Ciklus vége
Eljárás vége.

Vonalvég(I,X,Y,Z):      [Z a vonal végpontja - belső pont]
  Z:=Y
  Ciklus amíg üres(X,Z+I)
    Z:=Z+I
  Ciklus vége
Eljárás vége.

A feladat nemrekurzív változata ennél jóval bonyolultabb lesz. Itt verembe tesszük a megrajzolandó vonal végpontjai koordinátáit, miközben az előbb megrajzolt szakasz oldalait járjuk be, s csak ezután fogunk hozzá a verem tetején levő szakasz tényleges feldolgozásához.

Festés(X,Y):
  Vonalvég(-1,X,Y,Y1): Vonalvég(1,X,Y,Y2)
  Verembe(X,Y1,Y2)
  Ciklus amíg a verem nem üres
    Veremből(X,Y1,Y2)
    Vonalrajzolás(X,Y1,X,Y2)
    Szomszéd oszlop(X-1,Y1,Y2)              [bal szomszéd]
    Szomszéd oszlop(X+1,Y1,Y2)              [jobb szomszéd]
  Ciklus vége
Eljárás vége.

Szomszéd oszlop(X,Yk,Yv):
  I:=Yk
  Ciklus amíg IYv
    Ha üres(X,I) akkor Vonalvég(-1,X,I,Y3): Vonalvég(1,X,I,Y4)
                       Verembe(X,Y3,Y4): I:=Y4+1
              különben I:=I+1
    Elágazás vége
  Ciklus vége
Eljárás vége.

G. Sokszög festés háromszögenként

Konvex sokszög mindig felbontható háromszögekre egy tetszőleges csúcsából kiin­dulva, így alkalmazható rá a felbontás (1., i-edik és i+1-edik csúcs), majd a háromszög­festés.

Konkáv sokszög esetén is alkalmazható a fenti eljárás, de ekkor a sokszögön kívüli területeket is befest ez az eljárás. Megállapíthatjuk ugyanakkor, hogy a sokszögön kívüli területeket mindig páros sokszor, a belülieket pedig páratlan sokszor festi. Ekkor XOR műveletet alkalmazva a festéskor, végeredményként éppen a befestett alakzatot kapjuk.

H. Sokszög festés metsző vonalakkal

A képernyő széléről a másik széle felé haladva számoljuk, hogy hány határoló szaka­szon haladunk át! A belső pontokban ez a szám mindig páros, a külső pontokban pedig páratlan. Kivételt jelentenek sajnos a vízszintes szakaszokat, illetve alsó vagy felső csúcs­pontokat tartalmazó sorok. A megoldás: ne a képponotokon, hanem ponotsan két kép­pont között húzzuk a képzeletbeli vonalat, s ez alapján figyeljünk a párosságra, páratlan­ságra!

Egy másik megoldásnál szűmoljuk ki az összes (nem vízszintes) határoló szakasz és képernyő vízszintes szakaszai metszéspontjait, majd ezeket képernyő soronként ren­dezzük sorba! Ekkor minden esetben páratlan sorszámú ponttól a következő páros sor­számúig kell egy vízszintes szakaszt rajzolni a képernyőre.

 

5. Vágás (Cohen-Sutherland)

Ha az alakzat nagyobb, mint a képernyő, akkor az alakzat képernyőn kívüli részét le kell vágni. Az alakzat és a képernyő viszonya a következő lehet:

Az ábrán az A szakasz teljes egészében látszik a képen, a B-nek csak az egyik része látható, a C-nek csak egy középső darabja látszik, a D pedig egyáltalán nem látszik. Ez a négy eset sokféle­képpen fordulhat elő. A felada­tunk ezek vizsgálata, s a szüksé­ges vágások elvégzése lesz.

Egészítsük ki a képet az egész képmezőre, s rendeljünk egy négy bites kódot minden mezőhöz:

A kódolás célja az, hogy elkerüljük nagyon sok logikai feltétel vizsgálatát.

Ha egy szakasz mindkét végpontjának kódja 0000, akkor a teljes szakasz látszik, ha a végpon­tok kódjával végrehajtott logikai ÉS művelet eredménye nem 0, akkor a szakasz biztosan nem látszik (a kódokat ezért választottuk ilyennek). Ha nem ezek az esetek állnak fenn, akkor a szakaszt a képernyő egyik élével alkotott metszéspontjánál kettévágjuk. Az így kapott egyik szakasz biztosan a képernyőn kívül lesz, a másikra pedig újra el kell végezni a fenti eljárást (ugyanis a 0001-ből 1000-ba húzott szakasz vagy metszi a képernyő egyik élét, vagy nem).

Megjegyzés: A nagybetűs logikai műveletek egész számokra vonatkozó bitenkénti műveleteket jelentenek.

Legyen a képernyő felső sorának y-koordinátája KF, alsó sorának pedig KA, a baloldali szél x-koordinátája KB, a jobboldalié pedig KJ!

Vágóalgoritmus(X1,Y1,X2,Y2):
  Végpontok kódjának előállítása(C1,C2)
  Ciklus amíg nem ( (C1=0 és C2=0) vagy (C1 ÉS C2)=0 )
    Ha C1=0 akkor Csere(C1,X1,Y1,C2,X2,Y2)
    Ha (C1 ÉS 1)=1 akkor Vágás a felső szélen
    Ha (C1 ÉS 2)=1 akkor Vágás a jobbszélen
    Ha (C1 ÉS 4)=1 akkor Vágás az alsó szélen
    Ha (C1 ÉS 8)=1 akkor Vágás a balszélen
    Végpontok kódjának előállítása(C1,C2)
  Ciklus vége
  Ha C1=0 és C2=0 akkor Szakasz rajzolás(X1,Y1,X2,Y2)
Eljárás vége.

Végpontok kódjának előállítása(C1,C2):
  C1:=0 : C2:=0
  Ha Y1>KF akkor C1:=C1 VAGY 1
  Ha Y2>KF akkor C2:=C2 VAGY 1
  Ha X1>KJ akkor C1:=C1 VAGY 2
  Ha X2>KJ akkor C2:=C2 VAGY 2
  Ha Y1<KA akkor C1:=C1 VAGY 4
  Ha Y2<KA akkor C2:=C2 VAGY 4
  Ha X1<KB akkor C1:=C1 VAGY 8
  Ha X2<KB akkor C2:=C2 VAGY 8
Eljárás vége.

A vágáshoz mindig két szakasz metszéspontjának koordinátáit kell kiszámítani.

Vágás a felső szélen:
  X1:=X1+(X2-X1)*(KF-Y1)/(Y2-Y1) : Y1:=KF
Eljárás vége.

Vágás az alsó szélen:
  X1:=X1+(X2-X1)*(KA-Y1)/(Y2-Y1) : Y1:=KA
Eljárás vége.

Vágás a jobbszélen:
  X1:=KJ : Y1:=Y1+(Y2-Y1)*(KJ-X1)/(X2-X1)
Eljárás vége.

Vágás a balszélen:
  X1:=KB : Y1:=Y1+(Y2-Y1)*(KB-X1)/(X2-X1)
Eljárás vége.