Filling – Umplerea poligoanelor [605858]
Cuprins Not iuni generale Algoritm scan line de umplere
Filling – Umplerea poligoanelor
Marian Ioan MUNTEANU
Al.I.Cuza University of Iasi, Romania
webpage: http://www.math.uaic.ro/ munteanu
12 Noiembrie 2012
Cuprins Not iuni generale Algoritm scan line de umplere
Cuprins
1Not iuni generale
2Algoritm scan line de umplere
Cuprins Not iuni generale Algoritm scan line de umplere
O caracteristic a important a a gra cii raster fat a de gra ca
vectorial a este posibilitatea utiliz arii elementelor gra ce pline , adic a
solide.
Procesul se bazeaz a pe o carent a a sistemului vizual uman si
anume: integrarea spat ial a ^ ntre obiecte pe care ochiul nu este ^ n
stare s a le disting a din cauza absent ei rezolut iei.
Num arul receptorilor vizuali ind limitat, dac a se deseneaz a
elemente gra ce distincte dar su cient de aproape (cum ar doi
pixeli pe un monitor CRT) – ochiul va putea s a le perceap a ca pe
un singur obiect.
O mult ime de pixeli de aceea si culoare, unul l^ ang a altul, va
a sadar v azut a, de c atre ochiul uman, ca o singur a gur a colorat a
uniform.
Cuprins Not iuni generale Algoritm scan line de umplere
O caracteristic a important a a gra cii raster fat a de gra ca
vectorial a este posibilitatea utiliz arii elementelor gra ce pline , adic a
solide.
Procesul se bazeaz a pe o carent a a sistemului vizual uman si
anume: integrarea spat ial a ^ ntre obiecte pe care ochiul nu este ^ n
stare s a le disting a din cauza absent ei rezolut iei.
Num arul receptorilor vizuali ind limitat, dac a se deseneaz a
elemente gra ce distincte dar su cient de aproape (cum ar doi
pixeli pe un monitor CRT) – ochiul va putea s a le perceap a ca pe
un singur obiect.
O mult ime de pixeli de aceea si culoare, unul l^ ang a altul, va
a sadar v azut a, de c atre ochiul uman, ca o singur a gur a colorat a
uniform.
Cuprins Not iuni generale Algoritm scan line de umplere
O caracteristic a important a a gra cii raster fat a de gra ca
vectorial a este posibilitatea utiliz arii elementelor gra ce pline , adic a
solide.
Procesul se bazeaz a pe o carent a a sistemului vizual uman si
anume: integrarea spat ial a ^ ntre obiecte pe care ochiul nu este ^ n
stare s a le disting a din cauza absent ei rezolut iei.
Num arul receptorilor vizuali ind limitat, dac a se deseneaz a
elemente gra ce distincte dar su cient de aproape (cum ar doi
pixeli pe un monitor CRT) – ochiul va putea s a le perceap a ca pe
un singur obiect.
O mult ime de pixeli de aceea si culoare, unul l^ ang a altul, va
a sadar v azut a, de c atre ochiul uman, ca o singur a gur a colorat a
uniform.
Cuprins Not iuni generale Algoritm scan line de umplere
O caracteristic a important a a gra cii raster fat a de gra ca
vectorial a este posibilitatea utiliz arii elementelor gra ce pline , adic a
solide.
Procesul se bazeaz a pe o carent a a sistemului vizual uman si
anume: integrarea spat ial a ^ ntre obiecte pe care ochiul nu este ^ n
stare s a le disting a din cauza absent ei rezolut iei.
Num arul receptorilor vizuali ind limitat, dac a se deseneaz a
elemente gra ce distincte dar su cient de aproape (cum ar doi
pixeli pe un monitor CRT) – ochiul va putea s a le perceap a ca pe
un singur obiect.
O mult ime de pixeli de aceea si culoare, unul l^ ang a altul, va
a sadar v azut a, de c atre ochiul uman, ca o singur a gur a colorat a
uniform.
Cuprins Not iuni generale Algoritm scan line de umplere
Problem a
Se consider a un poligon dat prin intermediul v^ arfurilor sale.
S a se deseneze pixelii care apart in acestuia.
Va trebui s a individualiz am secvent ele orizontale de pixeli cont inute
^ n primitiv a, algoritm numit de scan-line . Ideea este de a "mi sca" o
linie orizontal a din pozit ia cea mai de jos care intersecteaz a
poligonul c atre pozit ia cea mai de sus (cu o unitate la ecare pas)
si de a aplica un algoritm de scan-conversion pe linie, de ecare
dat a.
Cuprins Not iuni generale Algoritm scan line de umplere
Problem a
Se consider a un poligon dat prin intermediul v^ arfurilor sale.
S a se deseneze pixelii care apart in acestuia.
Va trebui s a individualiz am secvent ele orizontale de pixeli cont inute
^ n primitiv a, algoritm numit de scan-line . Ideea este de a "mi sca" o
linie orizontal a din pozit ia cea mai de jos care intersecteaz a
poligonul c atre pozit ia cea mai de sus (cu o unitate la ecare pas)
si de a aplica un algoritm de scan-conversion pe linie, de ecare
dat a.
Cuprins Not iuni generale Algoritm scan line de umplere
Exemplu
Pentru a desena un dreptunghi plin, cu laturile paralele cu axele de
coordonate, vor trebui iluminat i pixelii interiori dreptunghiului
for yfrom ymintoymax of the rectangle (y scan-line)
for xfrom xmintoxmax (pixel cu pixel ^ n span)
putpixel (x;y;color )
Cuprins Not iuni generale Algoritm scan line de umplere
Exemplu
Pentru a desena un dreptunghi plin, cu laturile paralele cu axele de
coordonate, vor trebui iluminat i pixelii interiori dreptunghiului
for yfrom ymintoymax of the rectangle (y scan-line)
for xfrom xmintoxmax (pixel cu pixel ^ n span)
putpixel (x;y;color )
Cuprins Not iuni generale Algoritm scan line de umplere
Problema general a
Scopul nostru este de a construi un algoritm generic capabil s a
fac a " lling" pentru poligoane de orice tip: concave, convexe, cu
laturi care se intersecteaz a:
Cuprins Not iuni generale Algoritm scan line de umplere
Regula par { impar
Se a
a un punct ^ n interiorul unui poligon?
dintr-un punct arbitrar Pse deseneaz a o semidreapt a
se num ar a intersect iile cu laturile
punctul Peste interior dac a num arul de intersect ii este impar.
Cuprins Not iuni generale Algoritm scan line de umplere
Regula par { impar
Se a
a un punct ^ n interiorul unui poligon?
dintr-un punct arbitrar Pse deseneaz a o semidreapt a
se num ar a intersect iile cu laturile
punctul Peste interior dac a num arul de intersect ii este impar.
Cuprins Not iuni generale Algoritm scan line de umplere
Regula par { impar
Se a
a un punct ^ n interiorul unui poligon?
dintr-un punct arbitrar Pse deseneaz a o semidreapt a
se num ar a intersect iile cu laturile
punctul Peste interior dac a num arul de intersect ii este impar.
Cuprins Not iuni generale Algoritm scan line de umplere
Regula par { impar
Se a
a un punct ^ n interiorul unui poligon?
dintr-un punct arbitrar Pse deseneaz a o semidreapt a
se num ar a intersect iile cu laturile
punctul Peste interior dac a num arul de intersect ii este impar.
Cuprins Not iuni generale Algoritm scan line de umplere
Regula par { impar
Se a
a un punct ^ n interiorul unui poligon?
dintr-un punct arbitrar Pse deseneaz a o semidreapt a
se num ar a intersect iile cu laturile
punctul Peste interior dac a num arul de intersect ii este impar.
Cuprins Not iuni generale Algoritm scan line de umplere
Exemplu:
Cuprins Not iuni generale Algoritm scan line de umplere
Modalitatea cea mai la ^ ndem^ an a de a calcula intersect iile este s a
se utilizeze scan-conversion pentru liniile corespunz atoare ec arei
laturi a poligonului.
Aceast a aproximat ie poate s a produc a rezultate incorecte deoarece
algoritmul de rasterizare pentru linii nu are not iunea conceptului de
^ n auntru (interior) si ^ n afar a (exterior) si astfel pot select ionat i
pixeli care se a
e ^ n afara poligonului.
Aceasta este ^ n particular de nedorit c^ and avem de convertit
poligoane de culori diferite cu laturi comune: ^ n acest a manier a vor
exista pixeli ai unui poligon care "invadeaz a" alt poligon gener^ and
astfel un efect vizual incorect.
Cuprins Not iuni generale Algoritm scan line de umplere
Modalitatea cea mai la ^ ndem^ an a de a calcula intersect iile este s a
se utilizeze scan-conversion pentru liniile corespunz atoare ec arei
laturi a poligonului.
Aceast a aproximat ie poate s a produc a rezultate incorecte deoarece
algoritmul de rasterizare pentru linii nu are not iunea conceptului de
^ n auntru (interior) si ^ n afar a (exterior) si astfel pot select ionat i
pixeli care se a
e ^ n afara poligonului.
Aceasta este ^ n particular de nedorit c^ and avem de convertit
poligoane de culori diferite cu laturi comune: ^ n acest a manier a vor
exista pixeli ai unui poligon care "invadeaz a" alt poligon gener^ and
astfel un efect vizual incorect.
Cuprins Not iuni generale Algoritm scan line de umplere
Modalitatea cea mai la ^ ndem^ an a de a calcula intersect iile este s a
se utilizeze scan-conversion pentru liniile corespunz atoare ec arei
laturi a poligonului.
Aceast a aproximat ie poate s a produc a rezultate incorecte deoarece
algoritmul de rasterizare pentru linii nu are not iunea conceptului de
^ n auntru (interior) si ^ n afar a (exterior) si astfel pot select ionat i
pixeli care se a
e ^ n afara poligonului.
Aceasta este ^ n particular de nedorit c^ and avem de convertit
poligoane de culori diferite cu laturi comune: ^ n acest a manier a vor
exista pixeli ai unui poligon care "invadeaz a" alt poligon gener^ and
astfel un efect vizual incorect.
Cuprins Not iuni generale Algoritm scan line de umplere
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Descrierea algoritmului
Operat ia de lling pentru o singur a scan-line const a ^ n 3 pa si:
1.Se calculeaz a intersect iile dintre scan-line si toate laturile
poligonului.
2.Se ordoneaz a intersect iile dup a abscisa x.
3.Se aprind pixelii ^ ntre perechi de intersect ii care sunt interioare
poligonului, utiliz^ and, pentru a determina care pixel este interior,
a sa-numita regul a odd-parity care spune:
a) paritatea init ial a este par a;
b) ecare intersect ie schimb a paritatea;
c) se deseneaz a pixelii c^ and paritatea este impar a;
d) nu se deseneaz a nimic c^ and paritatea este par a.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
^Inainte de a analiza problemele de intersect ie si sorting, s a vedem
cum se de ne ste, ^ n diferite situat ii, dac a un pixel este interior sau
nu poligonului.
Va trebui s a r aspundem la c^ ateva ^ ntreb ari:
A. Dac a o intersect ie cu o valoare generic a a lui xeste
rat ional a, cum determin am care dintre cei doi pixeli de pe
orizontal a (care ^ ncadreaz a punctul ideal) este cel c autat?
dac a ^ nt^ alnim o intersect ie c^ and venim din interiorul
poligonului (paritatea – parity bit – este impar a) rotunjim la
^ ntregul mai mic pentru a r am^ ane tot ^ n auntru;
dac a venim din afara (exteriorul) poligonului (paritatea este
par a), rotunjim la ^ ntregul urm ator pentru a intra ^ n auntru.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
^Inainte de a analiza problemele de intersect ie si sorting, s a vedem
cum se de ne ste, ^ n diferite situat ii, dac a un pixel este interior sau
nu poligonului.
Va trebui s a r aspundem la c^ ateva ^ ntreb ari:
A. Dac a o intersect ie cu o valoare generic a a lui xeste
rat ional a, cum determin am care dintre cei doi pixeli de pe
orizontal a (care ^ ncadreaz a punctul ideal) este cel c autat?
dac a ^ nt^ alnim o intersect ie c^ and venim din interiorul
poligonului (paritatea – parity bit – este impar a) rotunjim la
^ ntregul mai mic pentru a r am^ ane tot ^ n auntru;
dac a venim din afara (exteriorul) poligonului (paritatea este
par a), rotunjim la ^ ntregul urm ator pentru a intra ^ n auntru.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
^Inainte de a analiza problemele de intersect ie si sorting, s a vedem
cum se de ne ste, ^ n diferite situat ii, dac a un pixel este interior sau
nu poligonului.
Va trebui s a r aspundem la c^ ateva ^ ntreb ari:
A. Dac a o intersect ie cu o valoare generic a a lui xeste
rat ional a, cum determin am care dintre cei doi pixeli de pe
orizontal a (care ^ ncadreaz a punctul ideal) este cel c autat?
dac a ^ nt^ alnim o intersect ie c^ and venim din interiorul
poligonului (paritatea – parity bit – este impar a) rotunjim la
^ ntregul mai mic pentru a r am^ ane tot ^ n auntru;
dac a venim din afara (exteriorul) poligonului (paritatea este
par a), rotunjim la ^ ntregul urm ator pentru a intra ^ n auntru.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
^Inainte de a analiza problemele de intersect ie si sorting, s a vedem
cum se de ne ste, ^ n diferite situat ii, dac a un pixel este interior sau
nu poligonului.
Va trebui s a r aspundem la c^ ateva ^ ntreb ari:
A. Dac a o intersect ie cu o valoare generic a a lui xeste
rat ional a, cum determin am care dintre cei doi pixeli de pe
orizontal a (care ^ ncadreaz a punctul ideal) este cel c autat?
dac a ^ nt^ alnim o intersect ie c^ and venim din interiorul
poligonului (paritatea – parity bit – este impar a) rotunjim la
^ ntregul mai mic pentru a r am^ ane tot ^ n auntru;
dac a venim din afara (exteriorul) poligonului (paritatea este
par a), rotunjim la ^ ntregul urm ator pentru a intra ^ n auntru.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
B. Cum se trateaz a cazul special al unei intersect ii cu
coordonate ^ ntregi? Pentru a evita con
icte de atribut ie pentru
laturi adiacente se de ne ste c a o intersect ie cu coordonate ^ ntregi
la limita din st^ anga pentru span de pixeli este intern a poligonului,
iar la limita din dreapta este extern a.
C. S i dac a intersect ia cu coordonate ^ ntregi se refer a la un
v^ arf? ^In calculul parit at ii se va considera doar v^ arful yminnu si
ymax al unei laturi.
D. Cum se trateaz a cazul special al v^ arfurilor care de nesc
laturi orizontale? Este de ajuns s a consider am c a v^ arfurile unei
linii orizontale nu in
uent eaz a calculul parit at ii si se obt ine
automat c a laturile orizontale de jos vor desenate, cele de sus nu.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
B. Cum se trateaz a cazul special al unei intersect ii cu
coordonate ^ ntregi? Pentru a evita con
icte de atribut ie pentru
laturi adiacente se de ne ste c a o intersect ie cu coordonate ^ ntregi
la limita din st^ anga pentru span de pixeli este intern a poligonului,
iar la limita din dreapta este extern a.
C. S i dac a intersect ia cu coordonate ^ ntregi se refer a la un
v^ arf? ^In calculul parit at ii se va considera doar v^ arful yminnu si
ymax al unei laturi.
D. Cum se trateaz a cazul special al v^ arfurilor care de nesc
laturi orizontale? Este de ajuns s a consider am c a v^ arfurile unei
linii orizontale nu in
uent eaz a calculul parit at ii si se obt ine
automat c a laturile orizontale de jos vor desenate, cele de sus nu.
Cuprins Not iuni generale Algoritm scan line de umplere
Probleme care apar
B. Cum se trateaz a cazul special al unei intersect ii cu
coordonate ^ ntregi? Pentru a evita con
icte de atribut ie pentru
laturi adiacente se de ne ste c a o intersect ie cu coordonate ^ ntregi
la limita din st^ anga pentru span de pixeli este intern a poligonului,
iar la limita din dreapta este extern a.
C. S i dac a intersect ia cu coordonate ^ ntregi se refer a la un
v^ arf? ^In calculul parit at ii se va considera doar v^ arful yminnu si
ymax al unei laturi.
D. Cum se trateaz a cazul special al v^ arfurilor care de nesc
laturi orizontale? Este de ajuns s a consider am c a v^ arfurile unei
linii orizontale nu in
uent eaz a calculul parit at ii si se obt ine
automat c a laturile orizontale de jos vor desenate, cele de sus nu.
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
^In gura considerat a, la scan-line 6 avem urm atoarea situat ie:
Init ial paritatea este par a. C^ and ajungem ^ n punctul (2 ;6) avem
intersect ie la limita din st^ anga, deci paritatea se schimb a si devine
impar a. Se ^ ncepe aprinderea pixelilor. Ajungem ^ n Fcare este
yminpentru ( FG) si ( EF) deci paritatea se schimb a de dou a ori si
astfel r am^ ane impar a. Se continu a aprinderea pixelilor. Ajungem
^ nCcare este maxim pentru ( BC) (nu in
uent eaz a paritatea), iar
latura ( CD) ind orizontal a, din nou nu schimb paritatea.
Continu am desenarea pixelilor.
Ajung ^ n Dcare este minim pentru
(DE), astfel paritatea devine par a.
Se ^ nceteaz a desenarea pixelilor.
(A sadar, pe segmentul orizontal
(CD) paritatea este impar a si prin
urmare, segmentul se traseaz a.)
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
Fiex[k],y[k] coordonatele v^ arfului Pkal poligonului si nnum arul
de laturi. Fie nr int num arul de intersect ii pe o anumit a scan line.
Fie de asemenea x int[k] abscisa intersect iei kcu scan line.
int x[100], y[100]; // coordonatele varfurilor
oat x int[100]; // coordonata x a intersectiilor
int u, k, n, nr int, ymin, ymax;
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
/* functie de calcul a marginii din stanga */
int stg(
oat z)
f /* daca z este intreg, il returneaza
daca z este rational, il rotunjeste la intregul urmator */
if (z == int (z)) return z;
else return int (z) + 1;
g
/* functie de calcul a marginii din dreapta */
int dr(
oat z)
f /* daca z este intreg, returneaza z-1
daca z este rational, il rotunjeste la intregul precedent */
if (z == int (z)) return z-1;
else return int (z);
g
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
/* functie de sortare */
oat *qsort (
oat *a, int L, int R)
f
int h, j;
oat temp;
for(h=L; h <=R-1; h++)
for(j=h+1; j <=R; j++)
if (a[h] >a[j])
f
temp=a[h];
a[h]=a[j];
a[j]=temp;
g
return a;
g
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
/* algoritmul de ll pe scan line */
void scanline(int y0)
f
int i;
nrint= 0;
for (i=1; i<=n; i++)
f
if ((y[i+ 1] y0)(y0 y[i])>0)
/* linia scan taie interiorul segmentului */
f
nrint++;
xint[nr
int]=(y0 y[i])
oat((x[i+1] x[i]))/
oat((y[i+1] y[i]))+x[i];
g
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
else if (y[i]==y0)
/* linia scan trece printr-un varf al poligonului */
if ((y[i-1] >y0) && (y[i+1] >y0))
f/* avem situatian/ pentru varfuri */
nrint+=2; /* consider varful Pi de doua ori */
xint[nr int-1]=x[i];
xint[nr int]=x[i];
g
else if ((y[i-1] y0)(y[i+1] y0)<0)
/* avem situatia laturilor una in continuarea celeilalte */
f
nrint ++;
xint[nr int]=x[i];
g
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
else if (y[i+1]==y0) /* avem latura orizontala */
if ((y[i+2] >y0) && (y[i-1] >y0))
f /* avem situatian=*/
nrint +=2;
xint[nr int-1]=x[i];
xint[nr int]=x[i+1];
gelse
if ((y[i+2] <y0)&&(y[i-1] >y0))
f /* avem cazul y[i]=y[i+1] intre y[i-1] >y[i+2] */
nrint++;
xint[nr int]=x[i];
gelse
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
if ((y[i+2] >y0)&&(y[i-1] <y0))
f/* avem cazul y[i]=y[i+1] intre y[i-1] <y[i+2] */
nrint++;
xint[nr int]=x[i+1];
g
g //end for
/* reamintim ca liniile orizontale se deseneaza daca sunt inferioare
si nu se deseneaza daca sunt linii orizontale superioare */
qsort(x int, 1, nr int);
// se sorteaza crescator abscisele intersectiilor
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
k=1;
while (k <nrint)
f
delay(10);
line(stg(x int[k]), y0, dr(x int[k+1]), y0);
k +=2;
g
g // end functie scanline
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
void main ( )f
clrscr( );
cout<<"Introduceti numarul de laturi:" <<endl;
cout<<"n=";
cin>>n;
cout<<"Introduceti coordonatele varfurilor:" <<endl;
for(k=1; k <=n; k++)
f
cout<<"x["<<k<<"]="; cin >>x[k];
cout<<"y["<<k<<"]="; cin >>y[k];
cout<<endl;
g
x[0]=x[n]; y[0]=y[n];
x[n+1]=x[1]; y[n+1]=y[1];
x[n+2]=x[2]; y[n+2]=y[2];
Cuprins Not iuni generale Algoritm scan line de umplere
Algoritmul
for(k=1; k <=n; k++)
line(x[k], y[k], x[k+1], y[k+1]);
/* a
area minimului si maximului pentru scan line */
ymin=x[1]; ymax=y[1];
for (k=1; k <=n; k++) if (y[k] >ymax) ymax=y[k];
for (k=1; k <=n; k++) if (y[k] <ymin) ymin=y[k];
/* ll pe scan line de la ymin la ymax */
for (u=ymin; u <= ymax; u++)
f
setcolor(u%5+1); // umplerea se face cu 5 culori
scanline(u);
g
Copyright Notice
© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.
Acest articol: Filling – Umplerea poligoanelor [605858] (ID: 605858)
Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.