实验2-多边形有效边表填充

实验目的：

了解多边形扫描线填充算法

掌握多边形有效边表的建立方法

掌握多边形扫描线填充算法的实现方法

实验原理：

多边形扫描线填充算法是一种基于扫描线的填充算法。该算法将多边形分解为若干个扫描线，对每条扫描线与多边形的交点进行判断，从而确定该点是否应该被填充。

多边形有效边表是多边形扫描线填充算法的重要数据结构，用于存储多边形的边信息。有效边表中包含两个链表，一条是活动边表，另一条是等待边表。

建立多边形有效边表的方法如下：

将多边形的各边按照从上到下的顺序排列

对于每条边，计算该边与扫描线的交点，并将交点的 x 坐标、y 坐标、斜率等信息存储在有效边表中

每次扫描线向下移动一个像素时，从等待边表中将新的边添加到活动边表中，并删除活动边表中与扫描线不再相交的边

活动边表中的边按照 x 坐标的增序排列，如果有两条边的 x 坐标相同，则按照斜率的增序排列

扫描线从上往下移动时，依次遍历活动边表中的相邻边，每两条边之间的 x 坐标就是该区域需要填充的范围

实验步骤：

Step 1：打开绘图软件

打开绘图软件，新建一个画布。在画布上绘制一个多边形。

Step 2：建立多边形有效边表

按照上述方法建立多边形有效边表，并将其存储在程序中。

Step 3：扫描线填充

对于每条扫描线，遍历活动边表中的相邻边，计算填充范围，并将该范围内的像素点填充。

Step 4：输出结果

输出填充后的多边形。

实验注意事项：

在建立多边形有效边表时，需要注意处理多边形的边界情况，如水平边、垂直边、重合边等。

在扫描线填充时，需要注意处理交点为整数的情况，避免像素点的坐标出现偏移。