Ch多邊形區(qū)域填充課件

YTU區(qū)域的表示邊界表示內點表示YTU區(qū)域的表示邊界表示內點表示1YTU區(qū)域填充算法種子-種子填充算法YTU區(qū)域填充算法種子-種子填充算法2YTU問題區(qū)域填充算法要求區(qū)域一定是______的連通YTU問題區(qū)域填充算法要求區(qū)域一定是______的連通3YTU4連通區(qū)域和8連通區(qū)域44p44(b)p的8-鄰接點88888p888(a)p的4-鄰接點圖5-33鄰接點的定義YTU4連通區(qū)域和8連通區(qū)域44p44(b)p的8-鄰接4YTU4連通區(qū)域:通過4個方向的運動遍歷區(qū)域8連通區(qū)域:通過8個方向的運動遍歷區(qū)域YTU4連通區(qū)域:5YTU圖5-32區(qū)域的邊界表示和內點表示(b)以內點表示的4-連通區(qū)域(d)以內點表示的8-連通區(qū)域YTU圖5-32區(qū)域的邊界表示和內點表示(b)以內點表示的6YTU圖5-32區(qū)域的邊界表示和內點表示(a)以邊界表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域YTU圖5-32區(qū)域的邊界表示和內點表示(a)以邊界表示的7YTU補充4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡相同4連通區(qū)域△號8連通區(qū)域△號×號YTU補充4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡8YTU區(qū)域填充算法內點表示--泛填充算法（Flood-fillAlgorithm） 邊界表示法--邊界填充算法（Boundary-fillAlgorithm）YTU區(qū)域填充算法內點表示--泛填充算法9YTU4-連通邊界填充算法步驟-棧結構實現(xiàn)輸入初值:種子點坐標(x,y)、填充色、邊界顏色種子像素入棧當棧非空時重復執(zhí)行如下操作(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點不是邊界色且未置成填充色，則把該像素入棧。YTU4-連通邊界填充算法步驟-棧結構實現(xiàn)輸入初值:100種子像素入棧0種子像素入棧111212BDCA入棧條件:不是邊界色且未置成填充色1212BDCA入棧條件:1245134531不是邊界色且未置成填充色45134531不是邊界色且未置成填充色13413431不是邊界色且未置成填充色413431不是邊界色且未置成填充色1461331不是邊界色且未置成填充色661331不是邊界色且未置成填充色615371331不是邊界色且未置成填充色7371331不是邊界色且未置成填充色716381331不是邊界色且未置成填充色899381331不是邊界色且未置成填充色89917YTU小結:4-連通邊界填充算法凡是棧中出現(xiàn)的元素都是等待被填充的填充步驟出棧置填充色4-鄰接點入棧(非邊界色,非填充色)☆Flash演示4連通邊界填充算法

YTU小結:4-連通邊界填充算法凡是棧中出現(xiàn)的元素都是等18YTU8-連通邊界填充算法步驟出棧置填充色8-鄰接點入棧(非邊界色,非填充色)YTU8-連通邊界填充算法步驟出棧19YTU簡單的邊界填充算法棧操作多棧的存儲空間大沿掃描線填充水平像素段的4-連通邊界填充算法

P131圖5-34Flash演示出棧置填充色-連續(xù)像素段入棧-當前掃描線相鄰的上下兩條掃描線的最左像素YTU簡單的邊界填充算法20YTU2.泛填充算法-棧結構實現(xiàn)算法輸入:種子點坐標(x,y)、填充色、內點顏色種子像素入棧；當棧非空時作如下操作：(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點，內點的顏色且未置成填充色，則把該像素入棧。YTU2.泛填充算法-棧結構實現(xiàn)算法輸入:種子點坐標211243569810117141315121716填充色:綠色內點顏色:橙色1243569810117141315121716填充色:2212435698101171413151217169124356981011714131512171692312435698101171413151217169124356981011714131512171692412435698101171413151217164BDCA1014812435698101171413151217164BDCA251243569810117141315121716BDCA1014841243569810117141315121716BDCA12612435698101171413151217163BDCA10148512435698101171413151217163BDCA2712435698101171413151217163BDCA10148512435698101171413151217163BDCA28124356981011714131512171631014810621243569810117141315121716310142912435698101171413151217163101481062124356981011714131512171631014301243569810117141315121716310148106124356981011714131512171631014311243569810117141315121716310148101112435698101171413151217163101432YTU☆Flash演示8連通泛填充算法

YTU☆Flash演示8連通泛填充算法

33YTU對比邊界填充算法(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點不是邊界色且未置成填充色，則把該像素入棧。泛填充算法(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點是內點的顏色且未置成填充色，則把該像素入棧。YTU對比邊界填充算法泛填充算法34YTU小結區(qū)域填充算法邊界填充算法(8連通,4連通)泛填充算法 (8連通,4連通)簡單種子填充算法基于掃描線的種子填充算法YTU小結區(qū)域填充算法邊界填充算法(8連通,4連通)35YTU小結算法步驟初始:種子入棧棧頂元素出棧填充該元素填充該元素所在掃描線尋找新的種子入棧4鄰接點/8鄰接點填充色/邊界色/內點色相鄰上下兩掃描線最左像素YTU小結算法步驟初始:種子入棧36YTU☆思考題p132☆課堂練習–區(qū)域填充YTU☆思考題p13237YTU區(qū)域的表示邊界表示內點表示YTU區(qū)域的表示邊界表示內點表示38YTU區(qū)域填充算法種子-種子填充算法YTU區(qū)域填充算法種子-種子填充算法39YTU問題區(qū)域填充算法要求區(qū)域一定是______的連通YTU問題區(qū)域填充算法要求區(qū)域一定是______的連通40YTU4連通區(qū)域和8連通區(qū)域44p44(b)p的8-鄰接點88888p888(a)p的4-鄰接點圖5-33鄰接點的定義YTU4連通區(qū)域和8連通區(qū)域44p44(b)p的8-鄰接41YTU4連通區(qū)域:通過4個方向的運動遍歷區(qū)域8連通區(qū)域:通過8個方向的運動遍歷區(qū)域YTU4連通區(qū)域:42YTU圖5-32區(qū)域的邊界表示和內點表示(b)以內點表示的4-連通區(qū)域(d)以內點表示的8-連通區(qū)域YTU圖5-32區(qū)域的邊界表示和內點表示(b)以內點表示的43YTU圖5-32區(qū)域的邊界表示和內點表示(a)以邊界表示的4-連通區(qū)域(c)以邊界表示的8-連通區(qū)域YTU圖5-32區(qū)域的邊界表示和內點表示(a)以邊界表示的44YTU補充4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡相同4連通區(qū)域△號8連通區(qū)域△號×號YTU補充4連通區(qū)域也可理解成8連通區(qū)域，但是兩者的邊界不盡45YTU區(qū)域填充算法內點表示--泛填充算法（Flood-fillAlgorithm） 邊界表示法--邊界填充算法（Boundary-fillAlgorithm）YTU區(qū)域填充算法內點表示--泛填充算法46YTU4-連通邊界填充算法步驟-棧結構實現(xiàn)輸入初值:種子點坐標(x,y)、填充色、邊界顏色種子像素入棧當棧非空時重復執(zhí)行如下操作(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點不是邊界色且未置成填充色，則把該像素入棧。YTU4-連通邊界填充算法步驟-棧結構實現(xiàn)輸入初值:470種子像素入棧0種子像素入棧481212BDCA入棧條件:不是邊界色且未置成填充色1212BDCA入棧條件:4945134531不是邊界色且未置成填充色45134531不是邊界色且未置成填充色50413431不是邊界色且未置成填充色413431不是邊界色且未置成填充色5161331不是邊界色且未置成填充色661331不是邊界色且未置成填充色652371331不是邊界色且未置成填充色7371331不是邊界色且未置成填充色753381331不是邊界色且未置成填充色899381331不是邊界色且未置成填充色89954YTU小結:4-連通邊界填充算法凡是棧中出現(xiàn)的元素都是等待被填充的填充步驟出棧置填充色4-鄰接點入棧(非邊界色,非填充色)☆Flash演示4連通邊界填充算法

YTU小結:4-連通邊界填充算法凡是棧中出現(xiàn)的元素都是等55YTU8-連通邊界填充算法步驟出棧置填充色8-鄰接點入棧(非邊界色,非填充色)YTU8-連通邊界填充算法步驟出棧56YTU簡單的邊界填充算法棧操作多棧的存儲空間大沿掃描線填充水平像素段的4-連通邊界填充算法

P131圖5-34Flash演示出棧置填充色-連續(xù)像素段入棧-當前掃描線相鄰的上下兩條掃描線的最左像素YTU簡單的邊界填充算法57YTU2.泛填充算法-棧結構實現(xiàn)算法輸入:種子點坐標(x,y)、填充色、內點顏色種子像素入棧；當棧非空時作如下操作：(1)棧頂像素出棧；(2)將出棧像素置成填充色；(3)檢查出棧像素的4-鄰接點，若其中某個像素點，內點的顏色且未置成填充色，則把該像素入棧。YTU2.泛填充算法-棧結構實現(xiàn)算法輸入:種子點坐標581243569810117141315121716填充色:綠色內點顏色:橙色1243569810117141315121716填充色:5912435698101171413151217169124356981011714131512171696012435698101171413151217169124356981011714131512171696112435698101171413151217164BDCA1014812435698101171413151217164BDCA621243569810117141315121716BDCA1014841243569810117141315121716BDCA16312435698101171413151217163BDCA10148512435698101171413151217163BDCA6412435698101171413151217163BDCA10148512435698101171413151217163BDCA651243569810117141315121716310148106212435698101171413151217163101466124356981011714131512171631014810621243569810117141315121716310146712435698101171413151217163101481061243569810117141315121716310146812435698101171413151217