扫描线填充算法

#include "mainwindow.h" #include "ui_mainwindow.h" #include<qpainter.h> #include<qpen.h> #include<vector> using namespace std; void UpdateAetEdgeInfo(edge& e){ e.newInX+=e.deltaX; } bool EdgeXiComarator(edge& e1,edge& e2){ return(e1.newInX<=e2.newInX); } bool IsEdgeOutOfActive(edge e,int y){ return (e.yMax==y); } //AET:活动边表 NET:新边表 point Points[PointNum]={{100,300},{800,100},{1000,500},{900,1000},{800,500},{50,900},{400,400}}; MainWindow::MainWindow(QWidget *parent) : QMainWindow(parent), ui(new Ui::MainWindow) { ui->setupUi(this); //设置背景颜色 QPalette palette=this->palette();//获取调色板 palette.setColor(QPalette::Window,QColor(255,255,255));//设置为白色 this->setPalette(palette);//重新设置调色板 } void MainWindow::paintEvent(QPaintEvent *event){ QPainter painter(this); //反走样 painter.setRenderHint(QPainter::Antialiasing,true); painter.setPen(QColor(1,1,1)); QPen pen=painter.pen(); pen.setWidth(5); painter.setPen(pen); for(int i=0;i<PointNum;i++) painter.drawLine(QPointF(Points[i%PointNum].x,Points[i%PointNum].y),QPointF(Points[(i+1)%PointNum].x,Points[(i+1)%PointNum].y)); pen.setWidth(0.5); painter.setPen(pen); //painter.setPen(); int ymax=Points[0].y; int ymin=ymax; for(int i=1;i<PointNum;i++){ if(ymax<Points[i].y) ymax=Points[i].y; if(ymin>Points[i].y) ymin=Points[i].y; } vector<list<edge> > slNet(ymax-ymin+1); //初始化新边表 对左顶点和右顶点区间进行修正 edge e; for(int j=0;j<PointNum;j++){ point ps=Points[j];//当前处理边的起点 point pe=Points[(j+1)%PointNum];//当前处理边的终点 point pss=Points[(j-1+PointNum)%PointNum];//起点的前一个相邻点 point pee=Points[(j+2)%PointNum];//终点的后一个相邻点 if(pe.y!=ps.y){ //跳过水平线 e.deltaX=(pe.x-ps.x)/(pe.y-ps.y); if(pe.y>ps.y){ // e.newInX=ps.x; if(pee.y>=pe.y)//左右顶点的情况 e.yMax=pe.y-1; else e.yMax=pe.y; slNet[ps.y-ymin].push_front(e); } else{ e.newInX=pe.x; if(pss.y>=ps.y) e.yMax=ps.y-1; else e.yMax=ps.y; slNet[pe.y-ymin].push_front(e); } } } list<edge> aet; for(int y=ymin;y<=ymax;y++){ //将扫描线对应的所有新边插入到aet中，插入操作保证aet还是有序表，应用插入排序的思想 for(list<edge>::iterator iter=slNet[y-ymin].begin();iter!=slNet[y-ymin].end();iter++) aet.push_back(*iter); //执行具体的填充动作，将aet中的边交点成对取出组成填充区间，根据“左闭右开”的原则对每个区间进行填充 int i=1; int FinalI=aet.size(); for(list<edge>::iterator iter=aet.begin();iter!=aet.end();iter++){ painter.drawLine(QPointF((*iter).newInX,y*1.0),QPointF((*(iter++)).newInX,y*1.0)); i++; if(i==FinalI-1) break; } // for(int k=0;k<aet.size()-1;k++){ // painter.drawLine(QPoint(aet..newInX,y*1.0),QPointF((*iter++).newInX,y*1.0)); // } //当当前扫描线的y与边的ymax相等时，将其从aet中删除 aet.remove_if(bind2nd(ptr_fun(IsEdgeOutOfActive),y));//remove_if:按指定条件删除元素 //bind2nd和bind1st函数用于将一个二元算子转换成一元算子，它们需要两个参数，要转换的bf和一个值v // ptr_fun将普通函数(两个参数，如果有多个参数，要改用boost::bind)适配成bind1st或bind2nd能够使用的functor，否则对bind1st或bind2nd直接绑定普通函数，则编译出错 //更新边表中的每项的newInX值，即根据扫描线的连贯性用deltaX对其进行修正，并且根据newInX从小到大的原则对更新后的aet表重新排序 //更新newInX for_each(aet.begin(),aet.end(),UpdateAetEdgeInfo); //根据newInX从小到大重新排序 aet.sort(EdgeXiComarator); } } MainWindow::~MainWindow() { delete ui; }