欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

四边形填充

程序员文章站 2022-04-01 18:42:22
...

四边形填充算,除了比较笨的洪流法外,就是扫描线法了

基本算法是:

(1)       求交,计算扫描线与多边形的交点

(2)       交点排序,对第2步得到的交点按照x值从小到大进行排序;

(3)       颜色填充,对排序后的交点两两组成一个水平线段,以画线段的方式进行颜色填充;

(4)       是否完成多边形扫描?如果是就结束算法,如果不是就改变扫描线,然后转第1步继续处理;

这里有详细的介绍:

多边形区域填充算法--扫描线填充算法(有序边表法)https://blog.csdn.net/dirtyman_/article/details/79878903

对于四边形填充,这里基于扫描线算法,进一步优化,去掉了有序表。

主要优化方法,是对算法第一步[计算扫描线与多边形的交点], 根据上下两条扫描线的相关性,使用上一条扫描线的起始点x和线段的斜率计算下一条扫描线的起始点。

伪代码如下:

void fillArea(olm::Pointf(&points)[4], uint8_t* map, int width, int height, int col,MsImage* binmap){
        struct _Line{
            float k;
            float ymax;
            float x;
        };
        _Line lines[4];
        // 找一个y最小的点,及最小的y和最大的y
        float ymin = points[0].y_;
        float ymax = points[0].y_;
        int mid = 0;
        for(int i=0;i<4;i++){
          if(points[i].y_<ymin){
            ymin = points[i].y_;
            mid = i;
          }
          if(points[i].y_>ymax){
            ymax = points[i].y_;
          }
        }

        printf("top point mid: %d\n", mid);
        
        // 以此点为线段起点,顺时针为4条边命名
        for (int i = 0; i < 4; i++) {
            int id0 = (mid + i) % 4;
            int id1 = (mid + i + 1) % 4;
            lines[id0].k = (points[id0].y_ - points[id1].y_) / -(points[id0].x_ - points[id1].x_);
            lines[id0].ymax = std::max(points[id0].y_, points[id1].y_);
            lines[id0].x = points[id0].x_;
            printf("xxx (%d,%d) 1/k:%.3f,  ymax: %f \n", id0, id1, lines[id0].k, lines[id0].ymax);
        }
        int l0 = (mid+3)%4;
        int l1 = mid;
         printf("xxx l0: %d, l1: %d \n", l0,l1);
        float x0 ,x1;
        //初始起始点为最顶的点
        int y = points[mid].y_;
        x0 = x1 = points[mid].x_;
        
         printf("xxx y: %d, x: %.3f, %.3f  \n",y, x0, x1);
         getchar();
        for(;y<ymax+0.5;y++){
            // h 条扫描线
            //计算水平线 y=y'与四边形的交点(1,或两个交点)
            int sx = std::min(x0,x1)+0.5;
            int ex = std::max(x0,x1)+0.5;
            for(int x = sx;x<ex;x++){
                map[x+y*width] = col;
            }
            if(y>=ymax){
              break;
            }
            //下一条扫描线,如果换到了另一条边上,更新边索引(为了更新斜率倒数)
            if((y+1)>lines[l0].ymax){
                l0--;
                l0=(l0+4)%4;
            }
            if((y+1)>lines[l1].ymax){
                l1++;
                l1=(l1+4)%4;
                x1 = lines[l1].x;
            }

            x0 -= 1/lines[l0].k;
            x1 -= 1/lines[l1].k;

        printf("xxx l:%d,%d  x: %.3f, %.3f  \n",l0,l1,x0, x1);
    //  MsEncodeFile(binmap, "bin.pgm", 85);
      // getchar();
        }
    }