區(qū)域填充在計(jì)算機(jī)圖形圖像處理中得到廣泛的應(yīng)用。本文實(shí)現(xiàn)了一種基于可行域
的圖案填充的方法。該算法能正確填充任意復(fù)雜形狀的輪廓, 并具有實(shí)現(xiàn)方便、速度快、算法簡單、易于理解等特點(diǎn), 此快速算法具有很大的應(yīng)用價(jià)值。
在圖形、圖像處理及圖形與圖像的轉(zhuǎn)換中，區(qū)域填充算法是一種十分重要的基本算法，
在實(shí)際中得到了廣泛的應(yīng)用【1】。尤其是在CAD 軟件中，常常需要在特定的區(qū)域內(nèi)填充圖案。
填充算法的適應(yīng)性及效率對應(yīng)實(shí)際應(yīng)用有著非常重要的意義。
傳統(tǒng)的區(qū)域填充算法有掃描線填充算法、種子填充算法、邊填充算法等。其中最簡單、
直觀的區(qū)域填充算法是傳統(tǒng)的遞歸算法，它具有程序簡單、表達(dá)清楚的優(yōu)點(diǎn)，但由于存在多層遞歸，系統(tǒng)堆棧反復(fù)進(jìn)出，就不可避免地造成了費(fèi)時(shí)、費(fèi)內(nèi)存的缺點(diǎn)【2】。掃描線填充算法的基本思想是用一系列平行直線去切割輪廓線,通常有成對的交點(diǎn)出現(xiàn),每對交點(diǎn)就代表掃描線與輪廓線的一個(gè)相交區(qū)間。但經(jīng)典的掃描線填充算法仍然存在不必要的重復(fù)操作。種子填充算法是在被填充的區(qū)域中預(yù)先設(shè)置一個(gè)種子像素,然后以該像素為起點(diǎn),按四向算法或八向算法搜索下一個(gè)像素,由此出發(fā)蔓延直到找到區(qū)域內(nèi)所有像素;該算法的缺點(diǎn)是種子點(diǎn)的找尋比較困難,有的像素可能被訪問多次,并且種子點(diǎn)的入棧和出棧也降低了算法的效率。
邊填充算法的基本思想是對于每一條掃描線和輪廓線的每個(gè)交點(diǎn),將該掃描線上交點(diǎn)右方的所有像素取補(bǔ)。它的優(yōu)點(diǎn)在于簡單,與邊的順序無關(guān);缺點(diǎn)是每個(gè)像素可能被訪問多次,也需要各掃描線與每條邊進(jìn)行求交運(yùn)算。
本文在文獻(xiàn)【3】的基礎(chǔ)上，將其提出的基于可行域的剖面線填充方法應(yīng)用在圖案填充，該方法可以填充任意形狀的區(qū)域。這種方法已經(jīng)成功應(yīng)用在某鞋底圖案編輯系統(tǒng)中，取得了良好的效果。