网站首页 > 知识剖析正文

多边形扫描线填充算法及TypeScript示例

nixiaole 2024-12-15 16:03:16 知识剖析 15 ℃

实现多边形区域内填充的一种算法是扫描线填充算法，扫描线从多边形底部逐行向上扫描，每一条扫描线与多边形相交，位于多边形区域内的线段逐像素进行填充，多边形最高点的扫描线完成填充后即完成了多边形的填充。

多边形可以由顶点序列来定义，因此可以很容易得到多边形的y轴坐标的上下界，上下界内的扫描线与多边形都有交点，直观来看，扫描线与多边形有偶数个交点，从左至右偶数起始的点与下一个相邻点之间的线段为多边形内的区域，应进行填充。
由此可见，实现扫描线填充算法的关键就是求扫描线与多边形的交点，但是将求交转换为可运行的算法并不是那么直观，下面就来梳理一下思路。

多边形的有序边表

首先，多边形与扫描线的交点并不都是如上图那样简单，如下图扫描线y‘刚好经过两条边的共享顶点，因此与多边形有4个交点，那么根据上面的规则可以得出线段1-2和2-1在多边形区域内，这种情况显然是正确的。而扫描线y也刚好经过两条边的共享顶点，如果继续按照上面的奇偶规则应得出线段1-2和2-1在多边形区域内，这显示是不正确的，真实情况是线段2-1在多边形外。

仔细观察可以发现它们的不同之处在于共享顶点一种在扫描线的同一侧，另一种分布在扫描线的两侧，同一侧的情况下计为两个交点，而在两侧的情况计为一个交点就可以纠正错误的线段区间判定结果。一个简单的处理办法是首先预处理多边形，针对临边单调递增或递减的情况，将其中一条边缩短处理（y轴坐标减1），这样计算交点时就不存在共享顶点的情况了。
其次，还有一种情况是水平边与扫描线有无穷多个交点且都与此边重合，水平边的情况可以直接忽略，并不会影响填充结果。

最后，一个好的算法需要尽量减少不必要的计算，顶点序列虽然可以定义一个多边形，但是如果每条扫描线都要重新解直线方程求交点是不必要的。可以利用直线的相关性减少计算，针对一条边而言，线段的斜率是恒定不变的，一旦得出多边形最低点与扫描线相交，后续扫描线与此边的交点坐标可以依次根据斜率通过求和得出（主要是求x坐标，因为下一条扫描线的y'=y+1）。

通过建立多边形的有序边表，可以建立包含有效处理扫描线的全部信息，关于有序边表有几个关键之处：

多边形的有序边表和多边形是等价的，也就是通过有序边表可以构建出完整的多边形。
忽略多边形的水平边。
通过缩短某些边来解决单调变化临边共享顶点相交问题。
有序边表以穿过多边形顶点的扫描线y坐标为编号，每条相交边记录边的最高点ymax、与扫描线交点x、边斜率的倒数。
下图展示了一个多边形有序边表的建立过程。

扫描线的活化边表

建立了多边形的有序边表之后，接下来就可以从多边形最底部逐像素向上处理扫描线，通过建立扫描线的活化边表来存储扫描线与多边形的相交边信息。活化边表非常类似于有序边表，活化边表存储的是扫描线和多边形相交的边的信息，每条相交边存储边的ymax、与扫描线交点x坐标、斜率的倒数，且按照x交点坐标从左至右的顺序存储，这样可以直接判定两两x坐标之间的区间为多边形内区域。
下图处理的第一条扫描线y=0与边e10、e9相交，扫描线刚好经过两边的顶点，有两个重合的交点，也就是说扫描线0的活化边表和多边形有序边表0对应的边的信息完全相同，直接就可以从有序边表0中取出ymax、x、斜率倒数的值。填充两个交点之间的像素，其实也就是一个像素点。

接下来处理下一条扫描线y=1，与e2、e11、e10、e9相交，共4个交点；其中与e2、e11首次有交点且交点信息与有序边表1完全相同，可以直接提取；与e10、e9的交点x坐标可以根据上一条扫描线活化边表中的x与斜率倒数相加计算得到，最后填充从左至右两两x坐标之间的区间完成此扫描线的处理。

继续向上处理扫描线，以y=4的扫描线为例，与e2、e11、e10、e9相交，共4个交点，没有穿过任何边的顶点，此时计算活化边表的x交点就是以上一条扫描线x坐标加斜率导出计算得出，用同样的填充规则完成此条扫描线的处理。

再继续向上处理扫描线，以y=5扫描线为例，和之前的扫描线不同之处在于，此扫描线穿过了e11、e10的上顶点，即与ymax坐标相同，完成此条扫描线的填充处理之后需要将边e11、e10剔除出活化边表。

后续的扫描线处理方法与前面的方法相同，直到扫描线穿过多边形最高边e5、e6的顶点之后，即完成了整个多边形的填充。

TypeScript实现多边形扫描线填充算法

index.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>多边形扫描线填充示例</title>
</head>
<body>
    <canvas id="canvas001" width="600" height="600"></canvas>
    <script src="./dist/app.js"></script>
</body>
</html>

app.ts

class Vector2 {
    x: number;
    y: number;
    constructor(x: number, y: number) {
        this.x = x;
        this.y = y;
    }
}

class WebGL {
    canvas: HTMLCanvasElement;
    ctx: CanvasRenderingContext2D;
    vertices: Array<any>;

    // 构造函数
    constructor(canvas: HTMLCanvasElement) {
        this.canvas = canvas;
        this.ctx = canvas.getContext("2d");    
        this.vertices = [];
    }
    // 将屏幕坐标系转换为常用的y轴向上的坐标系
    transToScreenXY(x: number, y: number) {
        return [x, this.canvas.height - y];
    }

    setFillStyle(r: number, g: number, b: number) {
        this.ctx.fillStyle = "rgba(" + r*255 +  "," +  g*255 + "," +  b*255 + "," + 1.0 + ")";
    }

    // 填充1x1像素的矩形（即一个像素大小）来实现单个像素颜色设置
    setPixel(x: number, y: number) {
        let [sx, sy] = this.transToScreenXY(x, y);
        this.ctx.fillRect(sx, sy, 1, 1);
    }

    // rgba指定的颜色清空整个canvas
    glClearColor(r: number, g: number, b: number, a:number) {
        this.ctx.fillStyle = "rgba(" + r*255 +  "," +  g*255 + "," +  b*255 + "," + a + ")";
        this.ctx.fillRect(0, 0, this.canvas.clientWidth, this.canvas.clientHeight);
    }

    glVertex2(x: number, y: number) {
        this.vertices.push([x, y]);
    }

    /*
    顶点序列定义多边形
    vertices: [[x0,y0],[x1,y1]...]
    */
    newPolygon(vertices: Array<any>) {
        for (let i = 0; i < vertices.length; i++) {
            this.glVertex2(vertices[i][0], vertices[i][1]);
        }
    }

    /* 预处理多边形的两条临边（忽略水平、缩短一条单调变化临边），返回一条有序边表
    * 临边：v0---v1---v2
    * 返回值：{"line": y, "edges": [[ymax, x, 1/m]..]}
    */
   preprocessAdjEdge(v0: Vector2, v1: Vector2, v2: Vector2) {
        if (v0.y == v1.y) {
            // v0-v1为水平边
            if (v1.y < v2.y) {
                return {
                    "line": v1.y,
                    "edges": [
                        [v2.y, v1.x, (v2.x - v1.x) / (v2.y - v1.y)],
                    ]
                };
            }
        } else if (v0.y > v1.y) {
            // v1 y值最小
            if (v1.y < v2.y) {
                let edges;
                if (v2.x > v0.x) {
                    edges = [
                        [v0.y, v1.x, (v0.x - v1.x) / (v0.y - v1.y)],
                        [v2.y, v1.x, (v2.x - v1.x) / (v2.y - v1.y)]
                    ];
                } else {
                    edges = [
                        [v2.y, v1.x, (v2.x - v1.x) / (v2.y - v1.y)],
                        [v0.y, v1.x, (v0.x - v1.x) / (v0.y - v1.y)]
                    ];
                }
                return {
                    "line": v1.y,
                    "edges": edges
                };
            } else if (v1.y > v2.y) {
                // 单调递减
                return {
                    "line": v1.y + 1,
                    "edges": [
                        [v0.y, v1.x, (v0.x - v1.x) / (v0.y - v1.y)],
                    ]
                };
            } else {
                // v1-v2为水平边，忽略
                return {
                    "line": v1.y,
                    "edges": [
                        [v0.y, v1.x, (v0.x - v1.x) / (v0.y - v1.y)],
                    ]
                };
            }
        } else {
            // 单调递增
            if (v1.y < v2.y) {
                return {
                    "line": v1.y + 1,
                    "edges": [
                        [v2.y, v1.x, (v2.x - v1.x) / (v2.y - v1.y)],
                    ]
                };
            } 
        }
    }

    /*
    升序插入有序边表
    edges_table: {"line": n, "edges": [[ymax, x, 1/m]...]}
    sorted_edge_list: [edges_table, ...]
    */
    insertToSortedEdgeList(edges_table, sorted_edge_list) {
        let line = edges_table["line"];
        let insert_index = 0;
        for (let i = 0; i < sorted_edge_list.length; i++) {
            let current_line = sorted_edge_list[i]["line"];
            if (line > current_line) {
                insert_index += 1;
            } else {
                break;
            }
        }
        sorted_edge_list = sorted_edge_list.slice(0, insert_index).concat(edges_table, 
                                sorted_edge_list.slice(insert_index, sorted_edge_list.length));
        return sorted_edge_list;
    }

    /*
    检查扫描线与多边形是否有新的交点，加入到活化边表
    */
    intersectEdgeList(line, active_edges, sorted_edge_list) {
        // 遍历有序边表, 检查是否有新增的与扫描线相交的边，是则加入活跃边表
        for (let i = 0; i < sorted_edge_list.length; i++) {
            // 遍历边
            let line_edges = sorted_edge_list[i];
            let start_line = line_edges["line"];
            for (let j = 0; j < line_edges["edges"].length; j++) {
                if (start_line == line) {
                    // ymax, x, 1/m
                    active_edges.push([
                        line_edges["edges"][j][0],
                        line_edges["edges"][j][1],
                        line_edges["edges"][j][2]
                    ]);
                }
            }
        }
        // 按照x从左到右排序
        active_edges.sort(function(a, b) {return a[1] - b[1]});
        return active_edges;
    }

    /*
    填充多边形
    */
    fillPolygon() {
        // 首先生成多边形有序边表,取ymin、ymax
        let sorted_edge_list = [];
        let v0, v1, v2;
        let scan_line_min = this.vertices[0][1];
        let scan_line_max = 0;
        for (let i = 0; i < this.vertices.length; i++) {
            if (this.vertices[i][1] < scan_line_min) {
                scan_line_min = this.vertices[i][1];
            }
            if (this.vertices[i][1] > scan_line_max) {
                scan_line_max = this.vertices[i][1];
            }
            // 获取临边v0、v1、v2
            if (i == 0) {
                v0 = new Vector2(this.vertices[this.vertices.length - 1][0], this.vertices[this.vertices.length - 1][1]);
                v1 = new Vector2(this.vertices[i][0], this.vertices[i][1]);
                v2 = new Vector2(this.vertices[i + 1][0], this.vertices[i + 1][1]);
            } else if (i == this.vertices.length - 1) {
                v0 = new Vector2(this.vertices[i - 1][0], this.vertices[i - 1][1]);
                v1 = new Vector2(this.vertices[i][0], this.vertices[i][1]);
                v2 = new Vector2(this.vertices[0][0], this.vertices[0][1]);
            } else {
                v0 = new Vector2(this.vertices[i - 1][0], this.vertices[i - 1][1]);
                v1 = new Vector2(this.vertices[i][0], this.vertices[i][1]);
                v2 = new Vector2(this.vertices[i + 1][0], this.vertices[i + 1][1]);
            }
            // 处理多边形的临边获取一条扫描线的有序边表
            let edges_table = this.preprocessAdjEdge(v0, v1, v2);
            // 按升序插入多边形的有序边表中得到整个多边形的有序边表
            if (edges_table) {
                sorted_edge_list = this.insertToSortedEdgeList(edges_table, sorted_edge_list);
            }
        }
        // active_edge_list记录当前扫描线活化边表
        let active_edge_list = [];
        // 从底部向上逐条处理扫描线，求扫描线的活化边表
        for (let y = scan_line_min; y <= scan_line_max; y++) {
            // new_active_edge_list记录新加入的活化边表
            let new_active_edge_list = [];
            // 遍历扫描线的活化边表[ymax, x, 1/m]
            for (let j = 0; j < active_edge_list.length; j++) {
                let [ymax, x, rslope] = active_edge_list[j];
                // 如果扫描线穿越此边则加入到new_active_edge_list
                if (y <= ymax) {
                    // x' = x + 1/m
                    x += rslope;
                    new_active_edge_list.push([ymax, x, rslope])
                }
            }
            // 检查是否有与多边形新相交的边，有则加入活化边表
            active_edge_list = this.intersectEdgeList(y, new_active_edge_list, sorted_edge_list);
            // 填充
            for (let i = 0; i < active_edge_list.length; i+=2) {
                let [x_start, x_end] = [active_edge_list[i][1], active_edge_list[i + 1][1]];
                for (let j = Math.ceil(x_start); j <= Math.ceil(x_end); j++) {
                    this.setPixel(j, y);
                }
            }
        }     
    }
}

var canvas = <HTMLCanvasElement>document.getElementById("canvas001");
var webgl = new WebGL(canvas);
webgl.glClearColor(0, 0, 0, 1);
// 定义填充色
webgl.setFillStyle(0, 0.8, 0.8);
// 定义多边形
webgl.newPolygon([[50,300], [140,530], [200,340], [200,580], [360,500], [430,340], 
    [560,430], [500,50], [360,180], [230,80], [120,80]])
webgl.fillPolygon();

运行效果如下

参考文献

[1]. 《计算机图形学》（第三版）Donald Hearn、M.PaulineBaker著，4.10 通用扫描线填充算法，P159页;

上一篇： HTML+JavaScript案例分享: 打造经典俄罗斯方块，详解实现全过程
下一篇： HTML5教程关于canvas的线条知识，可以这样总结方法

网站首页 > 知识剖析 正文