一种简单的图案填充算法

1947080 2009-08-11 | rar | 154 | 次下载 | 5积分

资料介绍

区域填充在计算机图形图像处理中得到广泛的应用。本文实现了一种基于可行域
的图案填充的方法。该算法能正确填充任意复杂形状的轮廓, 并具有实现方便、速度快、算法简单、易于理解等特点, 此快速算法具有很大的应用价值。
在图形、图像处理及图形与图像的转换中，区域填充算法是一种十分重要的基本算法，
在实际中得到了广泛的应用【1】。尤其是在CAD 软件中，常常需要在特定的区域内填充图案。
填充算法的适应性及效率对应实际应用有着非常重要的意义。
传统的区域填充算法有扫描线填充算法、种子填充算法、边填充算法等。其中最简单、
直观的区域填充算法是传统的递归算法，它具有程序简单、表达清楚的优点，但由于存在多层递归，系统堆栈反复进出，就不可避免地造成了费时、费内存的缺点【2】。扫描线填充算法的基本思想是用一系列平行直线去切割轮廓线,通常有成对的交点出现,每对交点就代表扫描线与轮廓线的一个相交区间。但经典的扫描线填充算法仍然存在不必要的重复操作。种子填充算法是在被填充的区域中预先设置一个种子像素,然后以该像素为起点,按四向算法或八向算法搜索下一个像素,由此出发蔓延直到找到区域内所有像素;该算法的缺点是种子点的找寻比较困难,有的像素可能被访问多次,并且种子点的入栈和出栈也降低了算法的效率。
边填充算法的基本思想是对于每一条扫描线和轮廓线的每个交点,将该扫描线上交点右方的所有像素取补。它的优点在于简单,与边的顺序无关;缺点是每个像素可能被访问多次,也需要各扫描线与每条边进行求交运算。
本文在文献【3】的基础上，将其提出的基于可行域的剖面线填充方法应用在图案填充，该方法可以填充任意形状的区域。这种方法已经成功应用在某鞋底图案编辑系统中，取得了良好的效果。