扫描线填充算法.doc

扫描线多边形填充: 1、填充的主要思想: struct Edge { float x; float Δ x; float ymin; Edge *next; }; Step1 : (初始化)将 ET 表中各元素置空,建立 ET 表 Step2 : (basket sort, 分桶分类) 为多边形 P 的每一条边建立边结构按该边的上端点的 y值y 上插入 ET 表中的第 y 上类(组) ,即插入 ET[y 上]. Step3 :( 初始化) AEL 置空//AEL=Null y:ET 表中非空元素的区域号最大值。 Step4 :扫描转化 while ( AEL or ET 非空) do { (边插入)如果 ET[y] 非空,则将 ET[y] 中各边插入 AEL 。 (排序)将 AEL 中的各边按照 x (若 x 相等按Δx 的递增顺序排序。 ( 如果 AEL 非空填色)将 AEL 中各边依次组成对, 在横坐标为 y 的扫描线上, 将以每对边的 x 坐标为端点的区间上填上多边形所需要的颜色. (下一条扫描线) y --。 (边删除)将 AEL 中满足 y=ymin 的边删除。 (边更新)将 AEL 中的各边 x 值更新, x=x+ Δx} 2、源程序 C++ 源代码: CScanLineView::CScanLineView() { num=0; StartFlag=0; EndFlag=0; OriFlag=0; WindowFlag=0; ln=0; rn=0; bn=0; tn=0; l=200; r=350; b=200; t=350; sflag=0; lflag=0; // TODO: add construction code here } CScanLineView::~CScanLineView() {} BOOL CScanLineView::PreCreateWindow(CREATESTRUCT& cs) { // TODO: Modify the Window class or styles here by modifying // the CREATESTRUCT cs return CView::PreCreateWindow(cs); } ///////////////////////////////////////////////////////////////////////////// // CScanLineView drawing void CScanLineView::OnDraw(CDC* pDC) { CScanLineDoc* pDoc = GetDocument(); ASSERT_VALID(pDoc); if(WindowFlag) { // SelectObject((HDC)*pDC,redPen); pDC->MoveTo(l,t); pDC->o(l,b); pDC->o(r,b); pDC->o(r,t); pDC->o(l,t); // SelectObject((HDC)*pDC,blackPen); } // TODO: add draw code for native data here } ////////////////