În cele mai multe aplicații, se folosește unul dintre cele mai importante avantaje ale dispozitivelor raster - posibilitatea de a umple ecranul.
Există două tipuri de umplere:
· În primul rând, ambele conectate printr-o operație interactivă, precum și pentru a programa sinteza imaginii, aceasta servește pentru a umple partea interioară a poligonului definit de coordonatele nodurilor sale.
· În al doilea rând, legate de operarea interactivă, servește pentru a umple o zonă care este delimitată de un pixel de delimitare cu un cod diferit de coduri de orice pixeli din interiorul regiunii sau pixel este vopsit cu un cod prestabilit;
În această secțiune, considerăm umplere algoritm poligon. Următoarea secțiune va discuta algoritmi umple câmpul.
Cea mai simplă metodă de umplere un poligon specificat de coordonatele vertex, este de a determina dacă pixelul curent face parte din interiorul poligonului. Dacă faceți parte, pixelul este stocat.
Se determină un poligon pixel apartine poate fi, de exemplu, numărând unghiul total de cu vârfuri la pixel când traversează conturul poligonului. Dacă pixelul este în interiorul unghiul este de 360 °. în cazul în care este - (. Fig) 0 °.
Fig. 0.4.1. Definirea pixelului poligon
Calcularea accesoriului trebuie să fie efectuată pentru toți pixelii de pe ecran, și ca majoritatea pixelilor este de natură să poligoane, atunci procesul este prea risipitor. Volumul de calcule inutile, în unele cazuri, este posibil să se reducă utilizarea unui înveliș dreptunghiular - dreptunghi minim de incorporare a obiectului de interes, dar toate aceleași calcule vor fi multe. O altă metodă de determinare a punctului de membru în interiorul poligonului vor fi discutate mai jos în studiul de tăiere piese conform algoritmului Cyrus-Beck.
algoritmi de umplere progresive sunt utilizate efectiv, pe baza faptului că pixelii vecine într-un rând este probabil aceeași și variază doar în cazul în care linia intersectează cu marginea poligon. Această coerență se numește linii raster (Yi linie de scanare. Yi + 1. Yi + 2 în Fig.). Este suficient să se determine X coordonatele intersecțiile liniilor de scanare cu nervuri. Cuplurile sortate punctele de intersecție a defini intervalele de turnare.
Fig. 0.4.2. umbrire poligon progresiva
În plus, în cazul în care marginile se intersectează rândul i-lea, atunci cel mai probabil se va intersecta de asemenea, linia i + 1. (Linia de scanare Yi și Yi + 1 prezentat în Fig. 0.2). Aceasta se numește coerența coastelor. În trecerea la o nouă linie de ușor pentru a calcula noul X-coordonata punctului de intersecție al nervurilor, folosind X-coordonata punctului de intersecție al vechi și tangenta unghiului de coaste:
(Tangenta unghiului de înclinare al nervurilor - k = dy / dx, deoarece dy = 1, atunci 1 / k = dx).
Modificarea valorii intervalelor de sădire apar numai atunci când vârful apare în linia de scanare.
Linii contabile și margini de coerență permite umplerea poligoane pentru a construi diverși algoritmi de scanare foarte progresivă. Numai acele margini sunt luate în considerare pentru fiecare linie de scanare care se intersectează linia. Acestea sunt date de o listă de muchii active (ATS). Când se trece la următoarea linie care urmează să fie traversată coaste recalculat-coordonatele X ale intersecțiilor. Atunci când se produce o linie de scanare noduri rearanjarea ATS. Coastele care nu mai sunt intersectează, sunt eliminate din PAC, precum și toate noile margini, a trecut linia sunt introduse în ea.
Diagrama generală generează în mod dinamic o listă de muchii active, precum și de umplere a poligonului de jos în sus, după cum urmează:Pentru fiecare margine în lista de muchii active sunt introduse:
Dacă găsiți apoi că lista de muchii active, este gol, umplutura este finalizată.
Anexa 5 prezintă două subrutine, poligoane pline - V_FP0 și V_FP1. În primul rând pune în aplicare (cel mai simplu) algoritmul activ. Acest program este destul de eficient, dar generează două sau de trei ori mai mare decât intrarea pixelilor. Este acceptabil pentru dispozitivele de ieșire mici, cum ar fi matrice imprimante cu jet de cerneală sau.
Spre deosebire de V_FP0, in V_FP1 program foloseste un algoritm mai complex pentru formarea lista muchiilor active oferind absența practic completă a duplicare (Fig.).
Fig. 0.4.3. Compara algoritmi de umplere a poligonului
0.4.2 Sortarea metodă de distribuire de numărare
După cum sa menționat deja, pentru aplicații, în principal legate de activitatea interactivă folosind algoritmi umple zona cu grund.
În acest fel sau altul specificat turnat regiune (recolorable), un cod de pixeli, care va rula umple și punctul în zona de la care să înceapă de umplere.
Prin intermediul zonelor de referință sunt împărțite în două tipuri:
· Boundary-sigur, a cerut sa (inchis) limita astfel încât limita codurilor pixelilor sunt diferite de coduri recolorable internă a zonei. Codurile de pe pixelii din interiorul zonei a impus două condiții - acestea trebuie să fie diferite de limitele codul pixelului și codul revopsire pixeli. În cazul în care într-o anumită limită regiune există o altă frontieră trasată de pixelii cu același cod ca și limita exterioară, partea corespunzătoare a regiunii nu ar trebui să fie revopsite;
· Pe plan intern definite, trase un singur cod de pixel. La completarea codului se înlocuiește cu un nou cod de umbrire.
Aceasta este diferența de bază de umplere zona însămânțat prin umplerea poligonului. În acest din urmă caz, avem imediat toate informațiile cu privire la limitarea dimensiunea ecranului ocupat de poligon. Prin urmare, definiția poligonului accesorii pixel bazate pe algoritmi de lucru rapid folosind linii coerente și marginile (a se vedea. Secțiunea anterioară). Algoritmii de asemenea, umple o zonă cu o sămânță, trebuie mai întâi pentru a citi pixeli, și apoi să stabilească dacă acesta aparține domeniului și în cazul în care aparține, apoi vopsi.
Umple zona sau limita acestuia - un set de pixeli conectat. Prin intermediul accesului la zonele adiacente ale pixelilor sunt împărțite în 4-biți și 8-conectat. Cele 4-conectate regiunile acces la pixeli învecinate se realizează în patru direcții - la stânga și la dreapta pe orizontală și pe verticală în sus și în jos. Regiunile 8 conectate în aceste zone sunt adăugate 4 mai diagonală. Folosind conectivitatea putem, trecerea de la punctul inițial, pentru a ajunge și vopsea tot câmpul de pixeli.
Este important de remarcat faptul că frontiera 8 este conectat (Fig. A) și în regiunea de frontieră, invers 8 conectată 4 este conectat (vezi. Fig. B) 4 x zonă dreptunghiulară conectat. De aceea, umplerea regiunii 8 Algoritmul conectat 4 conectat poate duce la „scurgere“ peste graniță și umplerea pixelilor dintr-o zonă adiacentă.
În general, regiunea 4-conectat putem umple atât algoritmul 4 și 8-conectat. Reciproca nu este adevărat. Deoarece zona în Fig. și putem fi umplut cu orice algoritm și regiunea din Fig. utilizat, format din două regiuni adiacente 4-conectate poate fi umplut doar algoritm 8 coerent.
Fig. 0.5.1. zone de conectare și limitele lor
Utilizarea zonelor de conectivitate și stiva pot construi algoritmi simpli umple zona definită de delimitare atât pe plan intern și. În [] sunt considerate foarte scurte rutine de umplere recursive. În [] - oarecum rutine mai iterative.
0.5.1 Algoritmul de umplere simplă
Această anexă oferă trei proceduri de turnare din zona de frontieră specifice însămânțate.
Prima procedură - V_FAB4R implementează un algoritm recursiv pentru umplere-4 conectat regiune algoritm plasat în [4] corespunzător.
A doua procedură - V_FAB4 implementează un algoritm iterativ pentru umplerea regiunii 4-conectat aproape de algoritmul este plasat într-un [3].
O trăsătură caracteristică a acestor algoritmi - un cost foarte ridicat de memorie pentru stiva de proces și duplicării multiplu de pixeli de intrare. Valorile tipice pentru mărimea stack (vezi. constantele MAX_STK am definit mai jos) de circa zece mii de octeți atunci când mărimea de ordinul a 70 × 70 pixeli, și este foarte puternic dependentă de mărimea suprafeței ocupate, configurația sa și punctul inițial. De exemplu, pentru a umple un pătrat cu latura egală cu 65 discrete, iar începutul punctului de turnare (20,20) în raport cu un unghi pătrat necesită 7938 octeți stivă.
Procedura a treia - Algoritmul V_FAST implementează umplerea progresivă însămânțate zona de delimitare definită mai aproape de algoritmul corespunzător [3]. O trăsătură distinctivă a acestor algoritmi - cantități mari de cod, costul mic de memorie pentru stivă și de lucru practic nici o dublare de pixeli de intrare. Valorile tipice pentru mărimea stack (vezi. constantele MAX_STK definite mai jos) de aproximativ sute de bytes.
0.17.1 V_FAB4R - umplere recursiv 4 x conectat regiune