扫描线多边形区域填充算法研究

Study on the Algrithm of Scanning Line Filling in Polygon Area

在CAD系统中,经常需要对封闭区域进行填充.对于一个功能完善的CAD系统而言,区域填充算法是十分重要的内容,同时该算法也是图形学的基本算法之一.单连通多边形是解决复杂区域填充问题的基础,从扫描线区域填充的原理、数据结构的设计、算法实现等几个方面进行了详细的分析.

In CAD System, filling something in the closed polygon is always needed. The algorithm of Area filling is very impor- tant to a well functional CAD System. At the same time, this algorithm is basic in Computer Graphics. The problem of complicat- ed area filling can be resoled by simply connected polygon. This paper analyzes the filling of complicated polygon, from the fol- lowing aspects ： principle of filling region based on scanning line, the design of data structure, the algorithm implementation.