姓名：李海广 学号：S130201036
作业二：扫描线填充算法
一、 算法实现环境
软件 函数库。
二、算法原理分析
扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫
描由多条首尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一
系列交点。将这些交点按照 坐标排序，将排序后的点两两成对，作为线段的
两个端点，以所填的颜色画水平直线。多边形被扫描完毕后，颜色填充也就完
成了。扫描线填充算法也可以归纳为以下 个步骤：
（） 求交，计算扫描线与多边形的交点；
（） 交点排序，对第 步得到的交点按照 值从小到大进行排序；
（） 颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进
行颜色填充；
（） 是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然
后转第 步继续处理。
整个算法的关键是第 步，需要用尽量少的计算量求出交点，还要考虑交
点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备
输出显示。
对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计
算量大，而且效率底下。观察多边形与扫描线的交点情况，可以得到以下两个
特点：
（） 每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交
计算；
（） 相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所
在直线的斜率有关；
因此，对于每一条扫描线，不必每次都对多边形的所有边进行求交。
三、程序运行及截图
本程序的多边形的顶点由鼠标点击生成，用鼠标左键在窗口中任意点击小
于 个点，这些点将被存入一个类数组，然后用一个循环语句取出这个数组
