摘要： 四叉树编码方法是目前图象处理和计算机图形学中的一种有效方法。本文给出了平面区域的四叉树转换算法,并把它应用到区域填充中去,得到一种具有线性空间复杂度和线性时间复杂度的算法,大大地改进了目前计算机图形学中常用的区域填充算法。本算法的特点是利用面积相关性,而且特别适合于封闭曲线所围成的区域,如圆和椭圆等区域。本文给出了判断点在多边形内外的算法,并对算法进行分析。

Abstract: Quadtree coding is currently a valuable method in image processing and computer graphics. In this paper, an algorithm from regions to quadtrees is applied to region filling with linear space complexity and linear time complexity, which updates greatly algorithms of regions filling available. This algorithm uses the coherence properties of regions and is especially suitable for regions bounded by closed curves, eg. circles, ellipses etc. A simple method of deciding if a point is in a convex region is proposed.