邊標(biāo)志算法中常見問題及解決方法

摘 要

本文針對傳統(tǒng)的邊標(biāo)志算法在遇到水平邊、狹長條以及極值點(diǎn)等情況時(shí)會(huì)出現(xiàn)錯(cuò)誤填充的現(xiàn)象，提出了一種新的改進(jìn)方法。改進(jìn)后的算法需要設(shè)置一個(gè)計(jì)量型變量label，訪問到一個(gè)像素點(diǎn)時(shí)將該像素點(diǎn)的label值加1，以完全區(qū)別邊界點(diǎn)與內(nèi)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法對上述問題僅使用標(biāo)記值加1的簡單操作便能夠有效的處理，使得改進(jìn)之后的算法在圖形圖像數(shù)據(jù)處理以及多媒體通信等范圍內(nèi)取得更加廣泛的適用基礎(chǔ)。

【關(guān)鍵詞】邊標(biāo)志算法 計(jì)算機(jī)圖形學(xué) 掃描轉(zhuǎn)換 區(qū)域填充

1 引言

多邊形填充是計(jì)算機(jī)圖形學(xué)中最基本的算法之一，而邊標(biāo)志算法是多邊形填充算法中一種非常簡單容易描述的算法。在掃描的過程中設(shè)置一個(gè)布爾變量Label表示當(dāng)前點(diǎn)的狀態(tài)，其初始值為假，對于每一個(gè)掃描范圍內(nèi)的像素點(diǎn)如果是多邊形邊界上的點(diǎn)，便將Label的值取反，當(dāng)Label的值為真時(shí)，便將當(dāng)前像素點(diǎn)填充為填充色。

邊標(biāo)志算法的這種思想是基于如矩形、橢圓等理想化規(guī)則圖形才能正確無誤的實(shí)現(xiàn)。但是在實(shí)際應(yīng)用中，由于計(jì)算機(jī)硬件設(shè)備的限制以及現(xiàn)實(shí)生活中各種圖形的特點(diǎn)，該算法在離實(shí)際應(yīng)用還有一定的距離。本文在深刻理解現(xiàn)有的邊標(biāo)志算法的基礎(chǔ)上，對算法在實(shí)現(xiàn)過程中可能出現(xiàn)的問題進(jìn)行分析，并給出一種相對簡單的解決方法。

2 算法的缺陷

2.1 極值點(diǎn)問題

多邊形的頂點(diǎn)同時(shí)屬于兩條邊，但是并不是所有的頂點(diǎn)都會(huì)出現(xiàn)錯(cuò)誤填充的現(xiàn)象。如果頂點(diǎn)不屬于極值點(diǎn)，則填充正常；否則在進(jìn)行掃描填充時(shí)會(huì)使變量Label的值一直為真，從而出現(xiàn)該點(diǎn)右側(cè)出現(xiàn)“拖尾”現(xiàn)象。如圖1所示。

2.2 水平邊問題

當(dāng)水平直線的像素點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，不會(huì)影響填充效果；當(dāng)像素點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，就會(huì)出現(xiàn)填充錯(cuò)誤，如圖2所示。

2.3 多邊形邊界線掃描轉(zhuǎn)換時(shí)的問題

邊標(biāo)志算法實(shí)現(xiàn)的第一步是對多邊形的邊界線做上標(biāo)記，但是這種情況在遇到邊界線斜率的絕對值小于1時(shí)，直線與同一掃描線之間的交點(diǎn)個(gè)數(shù)就有可能出現(xiàn)奇數(shù)，因此這種情況仍然會(huì)出現(xiàn)類似水平邊問題的填充異常現(xiàn)象。

2.4 狹長條問題

當(dāng)兩條相交直線的斜率非常接近時(shí)，其交點(diǎn)在數(shù)字顯示器上的交點(diǎn)便會(huì)出現(xiàn)多個(gè)像素點(diǎn)，這時(shí)頂點(diǎn)附近的若干個(gè)像素點(diǎn)同樣也會(huì)重合，與水平掃描線之間的連續(xù)交點(diǎn)個(gè)數(shù)也有可能出現(xiàn)奇數(shù)。因此，在進(jìn)行填充時(shí)同樣會(huì)出現(xiàn)類似于水平邊問題的填充異常現(xiàn)象，如圖3所示。

3 算法的改進(jìn)

對上述問題深入分析，可以發(fā)現(xiàn)之所以會(huì)出現(xiàn)填充異常現(xiàn)象，是因?yàn)閭鹘y(tǒng)的邊標(biāo)志算法沒有將普通的邊界點(diǎn)與上述問題中的像素點(diǎn)區(qū)別開來。本文提出的新的改進(jìn)方法的主要思想為：在對多邊形的每一條邊進(jìn)行光柵化時(shí)，使用label（初始值為0）標(biāo)記是否為多邊形的邊界，首先存儲(chǔ)單元中取出當(dāng)前像素點(diǎn)的label值，然后對當(dāng)前需要標(biāo)記的像素點(diǎn)的label值進(jìn)行加1，然后在存放到當(dāng)前像素點(diǎn)的label值的位置。依次對對每一條邊進(jìn)行光柵化。在對多邊形內(nèi)部區(qū)域進(jìn)行填充時(shí)，起先讀出當(dāng)前像素點(diǎn)的label值，當(dāng)前像素點(diǎn)的label值若是1，則讀取當(dāng)前像素點(diǎn)的水平方向的左側(cè)和右側(cè)像素點(diǎn)的label值，如果他們的值都為1，則布爾變量inner的值不變，否則取反。填充顏色時(shí)若當(dāng)前像素點(diǎn)的label值大于0或者inner為真時(shí)，則填充為填充色，不然填充為背景色。如對于圖1中的A點(diǎn)和B點(diǎn)，在對兩點(diǎn)所在邊界光柵化之后他們的label值等于2是大于1的，所以在填充顏色時(shí)將A和B點(diǎn)填充為填充色。又因?yàn)槠淝昂髢蓚€(gè)像素點(diǎn)的label值不都為1，所以inner的值仍為假，從而該點(diǎn)右邊的像素點(diǎn)不填充。

4 驗(yàn)證

通過多次實(shí)驗(yàn)的驗(yàn)證可以發(fā)現(xiàn)，改進(jìn)之后的算法避免了在掃描填充時(shí)反復(fù)調(diào)用邊表結(jié)構(gòu)的問題，僅僅使用對邊界像素點(diǎn)的標(biāo)記值加1的操作即可實(shí)現(xiàn)上述問題中多邊形的正常填充。無論從硬件實(shí)現(xiàn)還是從軟件實(shí)現(xiàn)，改進(jìn)后的邊標(biāo)志算法比原來算法在運(yùn)行效率上都有相當(dāng)?shù)奶岣摺?/p>

參考文獻(xiàn)

[1]D.F.羅杰斯（梁友棟，石教英，彭群生譯）.計(jì)算機(jī)圖形學(xué)的算法基礎(chǔ)[M].北京：科學(xué)出版社，1987.

[2]張志龍，李吉成，沈振康.一種新的快速復(fù)雜連通區(qū)域掃描線填充算法[J].計(jì)算機(jī)工程與應(yīng)用，2004，40（31）：6-8.

[3]吳章文，楊代倫，勾成俊，等.區(qū)域填充極點(diǎn)判別算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15（08）：979-983.

作者簡介

王利祥（1987-），男，河南省濮陽市人。碩士學(xué)位。主要研究方向?yàn)殡娮优c通信工程、嵌入式計(jì)算。

作者單位

河南護(hù)理職業(yè)學(xué)院網(wǎng)絡(luò)管理中心 河南省安陽市 455000