一種簡單的圖案填充算法

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