《计算机图形学》实验指导书高校教材  高清PDF影印版简介

（基于 VS2010 的 Visual C++版） （供测绘、遥感专业使用）

宋迎春（教授） 编著   2019 年 05 月

地球科学与信息物理学院测绘与遥感科学系

《计算机图形学》实验指导书高校教材 高清PDF影印版精彩内容节选

实验三 多边形的扫描转换与区域填充

一、实验目的

编写区域填充算法程序，验证算法的正确性。验证线型与线宽处理技术。

二、实验任务

1． 多边形有序边表算法程序设计；

2． 边填充算法和边标志填充算法；

3． 简单的种子填充算法和扫描线填充算法；

4． 区域填充图案程序设计；

三、实验步骤

1. 多边形的扫描转换

多边形可分为凸多边形、凹多边形、含内环多边形。

（1）凸多边形：任意两顶点间的连线均在多边形内。

（2）凹多边形：任意两顶点间的连线有不在多边形内的部分。

（3）含内环多边形：多边形内包含有封闭多边形。

扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要

求的颜色显示这些区间的像素。区间的端点可以通过计算扫描线与多边形边界线的交点获得。

对于一条扫描线，多边形的填充过程可以分为 4 个步骤。

（1）求交：计算扫描线与多边形各边的交点。

（2）排序：把所有交点按 x 值递增顺序排序。

（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个

相交区间。

（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。

具体实现方法：为多边形的每一条边建立一边表；为了提高效率，在处理一条扫描线时，

仅对与它相交的多边形的边进行求交运算。把与当前扫描线相交的边称为活性边，并把它们

按与扫描线交点递增的顺序存放在一个链表中，称此链表为活性边表。另外使用增量法计算

时，需要知道一条边何时不再与下一条扫描线相交，以便及时把它从扫描线循环中删除出去。

为了方便活性边表的建立与更新，为每一条扫描线建立一个新边表（NET），存放在该扫描

线第一次出现的边。为使程序简单、易读，这里新边表的结构应保存其对应边如下信息：当

前边的边号、边的较低端点（xmin，ymin）与边的较高端点（xmax，ymax）和从当前扫描线到

下一条扫描线间 x 的增量x。