多边形扫描转换(简化)

扫描线多边形填充算法扫描线多边形填充算法（Scanline Polygon Fill Algorithm）是一种计算机图形学中广泛使用的算法，用于将一个封闭的多边形形状涂色填充。

它通过扫描线的方式，从上到下将多边形内的像素按照预设的填充颜色来进行填充。

本文将详细介绍扫描线多边形填充算法的原理、流程和实现细节。

1.算法原理：扫描线多边形填充算法基于扫描线的思想，在水平方向上扫描每一行像素，并检测多边形边界与扫描线的交点。

通过将扫描线从上到下扫过整个多边形，对于每一行像素，找出与多边形边界交点的水平线段，然后根据填充颜色将像素点进行填充。

2.算法流程：-找出多边形的最小和最大Y坐标，确定扫描线的范围。

-从最小Y坐标开始，到最大Y坐标结束，逐行进行扫描。

-对于每一行，找出与多边形边界交点的水平线段。

-根据填充颜色，为每个水平线段上的像素点进行填充。

3.算法实现：-首先，需要根据给定的多边形描述边界的顶点坐标，计算出每条边的斜率、最小和最大Y值以及每条边的X坐标交点。

-然后，对于每一扫描线，找出与多边形边界交点的水平线段，即找出交点的X坐标范围。

-最后，根据填充颜色，将该范围内的像素点进行填充。

4.算法优化：- 针对复杂多边形，可以使用活性边表（AET，Active Edge Table）来管理边界信息，加快查找交点的速度。

-可以使用桶排序来排序边界事件点，提高扫描速度。

-根据多边形边的特征，对算法进行优化，减少不必要的计算和内存消耗。

5.算法应用：-扫描线多边形填充算法广泛应用于计算机图形学中的图形渲染、图像处理等领域。

-在游戏开发、CAD绘图、虚拟现实等应用中，扫描线多边形填充算法被用于快速绘制和渲染复杂多边形。

总结：扫描线多边形填充算法是一种经典的计算机图形学算法，通过扫描线的方式对多边形进行填充。

它可以高效地处理各种形状的多边形，包括凸多边形和凹多边形。

算法虽然简单，但在实际应用中具有广泛的用途。

计算机图形学——多边形的扫描转换（基本光栅图形算法）⼀、多边形扫描转换在光栅图形中，区域是由【相连的】像素组成的集合，这些像素具有【相同的】属性值或者它们位于某边界线的内部1、光栅图形的⼀个基本问题是把多边形的顶点表⽰转换为点阵表⽰。

这种转换成为多边形的扫描转换。

2、多边形的扫描转换与区域填充问题是怎样在离散的像素集上表⽰⼀个连续的⼆维图形。

3、多边形有两种重要的表⽰⽅法：（1）顶点表⽰：⽤多边形的定点序列来表⽰多边形优点：直观、⼏何意义强、占内存少、易于进⾏⼏何变换缺点：没有明确指出那些象素在多边形内，故不能直接⽤于上⾊（2）点阵表⽰：是⽤位于多边形内的象素集合来刻画多边形缺点：丢失了许多⼏何信息（eg:边界、顶点等）但是【点阵表⽰是光栅显⽰系统显⽰时所需的表现形式。

】多边形的扫描转换就是把多边形的顶点表⽰转换为点阵表⽰，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置相应的灰度或颜⾊。

实际上就是多边形内的区域的着⾊过程。

4、多边形分类⼆、X扫描线算法X扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的相交区间，再⽤要求的颜⾊显⽰这些区间的象素，即完成填充⼯作。

区间的端点可以通过计算扫描线与多边形边界线的交点获得。

如扫描线y=3与多边形的边界相交于4点（2,3）、（4,3）、（7,3）、（9,3）这四个点定义了扫描线从x=2到x=4，从x=7到x=9两个落在多边形内的区间，该区间内像素应取填充⾊。

算法的核⼼是按x递增顺序排列交点的x坐标序列。

由此可得到扫描线算法步骤如下：算法步骤：1.确定多边形所占有的最⼤扫描线数，得到多边形定点的最⼩最⼤值（y min和y max）；2.从y min到ymax每次⽤⼀条扫描线进⾏填充；3.对⼀条扫描线填充的过程分为四个步骤：a)求交点；b)把所有交点按递增顺序排序；c)交点配对（第⼀个和第⼆个，第三个和第四个）；d)区间填⾊。

描述多边形扫描转换的扫描线算法的基本步骤多边形扫描转换是计算机图形学中一种常用的算法，用于将输入的多边形进行转换和填充。

其基本步骤包括初始化，活性边表的生成，活性边表的更新和扫描线的处理。

1.初始化首先，需要根据输入的多边形构造一个扫描线填充的边表。

这包括对多边形顶点的排序、计算多边形中的水平线交点，并将边表中的数据初始化为初始值。

2.活性边表的生成活性边表是用来存储和管理与扫描线相交的边的数据结构。

生成活性边表的过程包括两个步骤：-遍历多边形的每一条边，将边与当前扫描线的位置进行比较，如果两者相交，则将这条边添加到活性边表中。

-对活性边表中的边按照交点的水平位置进行排序。

这里可以使用插入排序等算法。

3.活性边表的更新活性边表需要在每次扫描线移动时进行更新。

这包括对活性边表中的边进行更新，以反映新的交点或边的状态的变化。

-对于与当前扫描线相交的边，需要计算其交点，并更新到活性边表中。

-对于已经处理完的边或超出当前扫描线范围的边，从活性边表中移除。

4.扫描线的处理在每次扫描线移动时，需要对当前的活性边表进行处理。

这包括两个子步骤：-将活性边表中的边按照两两成对的方式遍历，找到当前扫描线和这两条边所定义的三角形的上顶点和下顶点。

-将这个三角形的内部填充，并进行显示或存储等处理。

5.继续扫描线的移动在处理完一条扫描线后，需要将扫描线的位置向上移动一个单位，并继续执行第3步和第4步，直到所有的扫描线都被处理完毕。

总结：多边形扫描转换的基本步骤包括初始化、活性边表的生成、活性边表的更新和扫描线的处理。

这个算法通常用于实现对多边形的填充。

在每次扫描线移动时，活性边表需要进行更新，以反映新的交点或变化的边的状态。

扫描线的处理包括遍历活性边表中的边，并根据扫描线和这两条边所定义的三角形的顶点来进行填充。

最后，重复执行扫描线的移动和对活性边表的更新和处理，直到所有的扫描线都被处理完毕。

多边形的扫描转换算法概述多边形的扫描转换算法是计算机图形学中用于将多边形转换为像素的常用算法。

它通过扫描线的方式来确定多边形与像素的相交关系，并将多边形的内部区域填充为指定的颜色。

本文将详细介绍多边形的扫描转换算法的原理、步骤和应用。

原理多边形的扫描转换算法基于扫描线的概念，将多边形的边界线与一条水平线或垂直线进行比较，从而确定多边形的内部和外部区域。

算法的关键在于边界线的处理和内部区域的填充。

步骤多边形的扫描转换算法一般包括以下步骤：1.初始化扫描线的位置和内部区域的填充颜色。

2.遍历多边形的边界线，将其与扫描线比较，确定内部和外部区域。

3.根据内部区域的状态，进行填充颜色。

4.更新扫描线的位置，继续扫描下一条线段，直至完成对所有边界线的处理。

算法详解初始化扫描线在开始进行多边形的扫描转换之前，需要初始化扫描线的位置和内部区域的填充颜色。

一般情况下，扫描线的位置可以从多边形的最低点开始，逐渐向上扫描。

内部区域的填充颜色可以根据具体需求进行选择。

边界线处理多边形的边界线可以由多个线段组成，需要按照一定的顺序进行处理。

一种常用的处理方式是按照边界线的上端点的纵坐标从小到大排序，然后依次处理每条线段。

对于每条线段，通过比较线段的上端点和下端点的纵坐标与扫描线的位置，可以确定线段与扫描线的相交关系。

根据线段的斜率可以进一步确定线段与扫描线的交点。

内部区域填充确定了线段与扫描线的相交关系后，就可以确定内部和外部区域。

一般情况下，内部区域被定义为线段上方的区域，而外部区域被定义为线段下方的区域。

根据内部区域的状态，可以进行填充颜色。

如果内部区域是连续的，则可以使用扫描线的颜色进行填充。

如果内部区域有间隙，则需要采用其他填充算法，如边界填充算法或种子填充算法。

更新扫描线处理完当前线段后，需要更新扫描线的位置，继续扫描下一条线段。

一般情况下，扫描线的位置会逐渐向上移动，直至到达多边形的最高点。

应用多边形的扫描转换算法在计算机图形学中有广泛的应用。

X-扫描线算法多边形的扫描转换（X-扫描线算法）⼀、两种表⽰⽅法把多边形的顶点表⽰转换为点阵表⽰称为多边形的扫描转换。

⼆、X-扫描线算法 图1 图21.步骤a. 求交b. 排序：把所有交点按递增顺序排序为何要进⾏排序？答：按交点x值递增排序，确保交点两两配对时填充区间的正确性。

c. 交点配对：确定填充区间d. 区间填⾊2.交点取舍（当扫描线与多边形顶点相交时，交点如何取舍？）两边只取1，同边0或2。

三、X-扫描线算法的改进1. 三⽅⾯的改进a. 处理⼀条扫描线，仅对与它相交的多边形的边（有效边）进⾏求交运算。

（也就是避免把所有的边都进⾏求交，因为⼤部分的边求交结果为空。

所以设置⼀个表来记录有效边。

即下⾯提到的AET）b. 考虑边的连贯性：当前扫描线与各边的交点顺序与下⼀条扫描线与各边的交点顺序很可能相同或⾮常相似。

c. 多边形的连贯性：当某条边与当前扫描线相交时，它很可能也与下⼀条扫描线相交。

2.数据结构通过引⼊新的数据结构来避免求交运算(1)活性边表a. 活性边表（AET）:把和当前扫描线相交的边称为活性边，并把它们按交点x坐标递增的顺序存于⼀个链表中。

b. 结点内容Δx=1/k，y max 是为了知道何时达到边界c. 举例(2)新边表(NET)建⽴AET需要知道与哪些边相交，所以定义NET来存储边的信息，从⽽⽅便AET的建⽴。

a. 构造⼀个纵向链表，长度为多边形占有的最⼤扫描线数。

每个节点（称为吊桶）对应多边形覆盖的⼀条扫描线。

b. 结点内容y max：该边的y最⼤值x min：该边较低点的x坐标c. NET挂在与该边较低端y值相同的扫描线吊桶中此时NET也就记录了6条有效边(3)NET与AET的使⽤流程⾸先我们得明⽩，AET的⽬的是为了使⽤增量⽅法避免求交运算，⽽NET是⽤在构造AET的。

a. 所以第⼀步为构造NET。

⽅法：遍历所有扫描线，把y min = i 的边放进NET[ i ]中，从⽽构造出整个NET。

多边形扫描转换算法多边形扫描转换算法是一种计算机图形学中常用的算法，用于将一个多边形转换为一组水平线段，以便进行填充或渲染。

该算法的基本思想是将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点，并将这些交点按照从左到右的顺序进行排序，最终得到一组水平线段。

多边形扫描转换算法的实现过程可以分为以下几个步骤：1. 找出多边形的顶点首先需要找出多边形的顶点，这些顶点可以通过遍历多边形的边来得到。

在遍历边的过程中，需要注意将相邻的边进行合并，以便得到多边形的完整轮廓。

2. 找出多边形与水平线段的交点在进行扫描转换时，需要将多边形沿着水平方向进行扫描，找出多边形与水平线段的交点。

这些交点可以通过遍历多边形的边来得到，对于每条边，需要判断其是否与当前扫描线相交，如果相交，则计算出交点的坐标。

3. 对交点进行排序得到多边形与水平线段的交点后，需要将这些交点按照从左到右的顺序进行排序。

这可以通过对交点的x 坐标进行排序来实现。

如果有多个交点具有相同的 x 坐标，则需要按照其 y 坐标进行排序。

4. 将交点组成线段将交点按照从左到右的顺序进行排序后，就可以将它们组成一组水平线段。

对于相邻的两个交点，可以将它们之间的部分作为一条水平线段。

如果两个交点之间没有其他交点，则可以将它们之间的部分作为一条水平线段。

5. 进行填充或渲染得到一组水平线段后，就可以进行填充或渲染。

对于填充操作，可以使用扫描线算法来实现。

对于渲染操作，可以将每条水平线段转换为一组像素点，并将这些像素点进行绘制。

多边形扫描转换算法的优点是可以处理任意形状的多边形，并且可以得到一组水平线段，方便进行填充或渲染。

但是该算法的缺点是需要进行大量的计算，特别是在多边形较复杂时，计算量会非常大，导致性能下降。

为了提高多边形扫描转换算法的性能，可以采用一些优化技术。

例如，可以使用空间分割技术来减少计算量，将多边形分割成多个小块进行处理。

另外，可以使用并行计算技术来加速计算过程，将多个处理器或计算机同时进行计算。

贵州大学计算机图形学实验报告学院：计算机科学与信息学院专业：软件工程班级：反映）根据扫描线的连贯性可知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。

所以，对所有的扫描线填充入点到出点之间的点就可填充多边形。

如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为3个步骤：(1)求出扫描线与多边形所有边的交点；(2)把这些交点按x坐标值以升序排列；(3)对排序后的交点进行奇偶配对，对每一对交点间的区域进行填充。

步骤(3)如上图：对y＝8的扫描线，对交点序列按x坐标升序排序得到的交点序列是(2,4,9,13)，然后对交点2与4之间、9与13之间的所有象素点进行填充。

求交点、排序、配对、填色利用链表：与当前扫描线相交的边称为活性边(Active Edge)，把它们按与扫描线交点x坐标递增的顺序存入一个链表中，称为活性边表AEL (AEL， Active Edge List)。

它记录了多边形边沿扫描线的交点序列。

AEL中每个对象需要存放的信息：ymax：边所交的最高扫描线；x：当前扫描线与边的交点；Δx：从当前扫描线到下一条扫描线之间的x增量next：指向下一对象的指针。

伪码：建立ET，置y为ET中非空桶的最小序号；置AEL表为空，且把y桶中ET表的边加入AEL表中；while AEL表中非空do begin对AEL表中的x、Δx按升序排列；按照AEL表中交点前后次序，在每对奇偶交点间的x段予以填充；计算下一条扫描线：y=y+1；if 扫描线y=ymax then 从AEL表中删除这些边；对在AEL表中的其他边，计算与下一条扫描线的交点：x=x +Δx 按照扫描线y值把ET表中相应桶中的边加入AEL表中；endend of algorithm二、区域填充算法：区域可采用两种表示形式:内点表示枚举区域内部的所有像素；内部的所有像素着同一个颜色；边界像素着不同的颜色。

边界表示：枚举出边界上所有的像素；边界上的所有像素着同一颜色；内部像素着不同的颜色。

多边形填充算法-有序边表法（扫描线算法）1.算法的基本思想（扫描线连贯性原理）： 对于⼀个给定的多边形，⽤⼀组⽔平(垂直)的扫描线进⾏扫描，对每⼀条扫描线均可求出与多边形边的交点，这些交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段；并且⼆者相间排列。

于是，将落在多边形内部的线段上的所有象素点赋以给定的⾊彩值。

算法中不需要检验每⼀个象素点，⽽只考虑与多边形边相交的交点分割后的扫描线段。

2.算法求解：对于每⼀条扫描线的处理：1）求交点：⾸先求出扫描线与多边形各边的交点；2）交点排序：将这些交点按X坐标递增顺序排序；3）交点匹配：即从左到右确定落在多边形内部的那些线段；4）区间填充：填充落在多边形内部的线段。

3.求交点的⽅法最简单的办法：将多边形的所有边放在⼀个表中，在处理每条扫描线时，从表中顺序取出所有的边，分别求这些边与扫描线的交点。

不使⽤该⽅法的原因：将做⼀些⽆益的求交点动作，因为扫描线并不⼀定与多边形的边相交，扫描线只与部分甚⾄较少的边相交；因此，在进⾏扫描线与多边形边求交点时，应只求那些与扫描线相交的边的交点。

确定与扫描线相交的边：⽤边表来确定哪些边是下⼀条扫描线求交计算时应该加⼊运算的。

4.边表（ET）：ET的意义在于为扫描线提供待加⼊的新边信息。

建⽴边的分类表ET(Edge Table)，每个结点结构如下：（Ymax ，ΔX ，X Ymin，）Ymax：边的最⼤Y值；ΔX：从当前扫描线到下⼀条扫描线之间的X增量（dX/ dY)；X Ymin：边的下端点的X坐标；next：指针，指向下⼀条边。

边的分类表可以这样建⽴：先按下端点的纵坐标(y值)对所有边作桶分类，再将同⼀组中的边按下端点X坐标递增的顺序进⾏排序, X坐标还相同的按ΔX递增的顺序进⾏排序。

5.活性边表AET把与当前扫描线相交的边称活化边AEL(Active Edge List) 。

组成的表称为活性表AET，其数据域组成如下：Ymax ：存放边的上端点Y坐标；X ：边与当前扫描线交点的X坐标；ΔX ，next指针：同边表。

一、填空题（每空1分，共20分）1、计算机地图制图可分为(数据获取)、（数据处理）、（图形输出）三个阶段.2、计算机地图制图系统由（硬件）、（软件）、（制图数据）、（地图模型与方法）以及（操作管理人员与应用人员）五个部分组成。

3、地图由（地图图形）和（文字标记）两部分组成。

4、地图从表现方式来看，包括（模拟地图）和（数字地图）两种形式。

5、地图按内容分，可分为（普通地图）和（专题地图）。

6、地图表示手段由（地图图形）、（地图色彩）、（地图文字）三部分组成。

7、数据的预处理主要内容有：（几何纠正）、（数据压缩）、（数据光滑）、（数据规范化）与（数据匹配）。

8、数据压缩的方法主要有（间隔取点法）、（垂距法和偏角法）、（道格拉斯—普客法）和（光栏法）。

9、图形的两种表示分别为（点阵表示（图像））与（矢量表示（图形））。

10、多边形的表示方法有（顶点表示）与（点阵表示）。

11、多边形的扫描转换方法有（逐点判断法）、（扫描线算法）、（边界标志算法）、（边缘填充算法）及(种子填充算法)。

13、区域填充算法的表示方法有（内点表示）及（边界表示）。

13、地图数据管理的三个阶段分别为：（程序管理阶段）、（文件管理阶段）、（数据库管理阶段）。

14、直线的裁剪算法常用的有（直接求交算法）、（编码裁剪算法）、（中点分割裁剪算法）。

15、多边形的裁剪算法包括（Sutherland-Hodgman算法）与（Weiler-Athenton裁剪算法）。

16、正轴测投影可分为（正等轴测投影）、（正二轴测投影）、（正三轴测投影）。

17、解析变换可分为（正解变换）、（反解变换）、（综合变换）三种。

18、地图符号系统由（图解语言）、（写出语言）、（自然语言）、（数学语言）组成。

19、矢量符号的绘制作方法有（编程法）、（信息法）。

20、线符号的绘制方法有两种即一是（重复配置点符号图元），二是（组合绘制）方法。

21、在数字制图中，常用到的宏运算有（扩张）、（侵蚀）、（加粗）、（减细）及（填充）。

计算机科学与技术学院2013－2014学年第一学期《计算机图形学》实验报告班级：学号：姓名：教师：成绩：实验项目（2、多边形的扫描转换与区域填充）一、实验目的与要求（1）了解多边形扫描转换的各种算法，掌握多边形的扫描转换与区域填充算法。

（2）进一步掌握在VC集成环境中实现图形算法的方法与过程。

二、实验内容设计菜单程序，利用消息处理函数，完成以下要求：（1）给出凸多边形的若干顶点（3 ~ 5个），实现多边形的“x扫描算法”。

（2）实现种子填充，泛填充算法（四邻法）。

（3）设计程序，实现判断一个点是否在多边形区域内部。

三、重要算法分析（一）边界表示的四连通区域种子填充算法此方法的基本思想是，从多边形内部任一像素出发，按照“左上右下”的顺序判断相邻像素，若不是边界像素且没有被填充过，则对其填充，并且重复上述过程，直到所有像素填充完毕。

(1)从种子点出发，向左判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。

(2)从种子点出发，向右判断多边形内部颜色，如果不是填充颜色并且不是边界颜色，则填充，直到遇到边界为止。

(3)将种子点的坐标y值上移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。

(4)将种子点的坐标y值下移一个像素，重复步骤（1）、（2）直到遇到上面边界为止。

（二）判断一个点是否在多边形内部解决方案是将测试点的y坐标与多边形的每一个点进行比较，我们会得到一个测试点所在的行与多边形边的交点的列表。

如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。

如图1所示，判断点（红点）y值左边与多边形有5个交点，右边与多边形有3个交点，则该点在多边形内部。

图1如图2所示，判断点（红点）y值左边与多边形有2个交点，右边与多边形有2个交点，则该点在多边形外部。

图2但是有一种特殊情况须特别处理一下，当与多边形顶点相交时，需要将改点计算为两个交点，如图3所示：图3四、程序运行截图1.种子四连通域填充法，如图4所示。

多边形扫描线填充算法的概念和步骤嘿，咱今儿个就来聊聊多边形扫描线填充算法。

你知道不，这就像是给多边形这个大拼图上色一样有趣呢！多边形啊，它可不是个乖乖待着的主儿，有好多边和角呢。

那这扫描线填充算法呢，就是来搞定怎么把这些多边形填满颜色的。

想象一下，有一条线就像个小刷子似的，从这头刷到那头，把多边形的每一块都照顾到。

这就是扫描线啦。

它一格一格地走，每到一个地方，就看看和多边形有啥关系。

那具体步骤呢，咱可得好好说说。

首先得确定这个多边形的边啊，知道它们在哪儿，长啥样。

然后呢，这条扫描线就开始工作啦，它会和多边形的边相交，这就像它们在打招呼呢。

接着，就根据这些交点来算出要填充的区域。

这就好比是知道了要给哪块地播种一样。

然后啊，就开开心心地把颜色填上。

你说这神奇不神奇？就这么一步一步的，一个多边形就被漂亮地填满啦。

这可不比画画简单哦，这里面可有大学问呢。

比如说吧，要是交点算错了，那颜色可就填错地方啦，那就成大花脸啦！所以每一步都得仔细着点呢。

而且啊，这算法就像个小魔法师，能让那些奇奇怪怪形状的多边形都变得漂漂亮亮的。

它能让我们在屏幕上看到各种好看的图形，这可都是它的功劳呀。

你再想想，要是没有这个算法，那我们看到的图形不就干巴巴的，一点都不生动啦。

多边形扫描线填充算法，虽然名字听起来有点拗口，但它真的超级重要呢。

它就像一个默默工作的小工匠，为我们打造出美丽的图形世界。

怎么样，现在对这个多边形扫描线填充算法是不是有点感觉啦？它可不简单哦，是计算机图形学里的一个宝贝呢！以后再看到那些好看的图形，可别忘了背后有它的功劳哟！。

多边形的填充——扫描线算法(原理)2007年10月05日星期五 11:52多边形在计算机中有两种表示：点阵表示和顶点表示。

顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。

点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，但具有面着色所需要的图像表示形式。

多边形填充就是把多边形的顶点表示转换为点阵表示，即从多边形的给定边界出发，求出位于其内部的各个像素，并将帧缓冲器内的各个对应元素设置为相应的灰度或颜色。

多边形填充最常用的方法就是扫描线算法。

下面分两篇文章介绍这种算法的原理和具体实现。

这里所介绍的算法只是针对非自交多边形，这些多边形可以是凸的、凹的或者带有空洞的。

所谓扫描线算法就是找到多边形的最小y值和最大y值，然后用这个范围内的每一条水平线与多边形相交，求得交点，再绘制线段。

所以我们只需要对一条水平线进行分析就可以。

很显然，一条扫描线和多边形有偶数个交点，将这些交点按照x值从小到大排列，然后取第1、2个绘制，第3、4个绘制......直到所有交点都被取完。

所以，对于一条扫描线，我们需要做的工作可以分为三个步骤：1)求出扫描线与多边形边的交点 2)将交点按照x升序排列 3)将排好序的交点两两配对，然后绘制相应线段。

这三个步骤中，后两个步骤很简单，没有特别的内容需要介绍。

但是第一个步骤比较麻烦。

这里有几个问题需要解决。

一是当扫描线与顶点相交时，交点的取舍。

当与那个顶点关联的边在扫描线同侧时，交点自然算两次，当与那个顶点关联的边在扫描线两侧时，交点只能算一次。

我们使用“下闭上开”的办法。

二是多边形边界上的像素取舍，我们采用“左闭右开”的办法。

三是如何减少计算量。

在绘制直线时，有一种DDA算法，它是利用(x,y)直接求出下一个点位于(x+1,y+m)或者(x+1/m, y+1)。

在这里可以利用这一点。

当已经得到y = e和多边形所有边的交点时，对于下一条扫描线y=e+1，如果没有新边与y=e+1相交，就可以推出y = e+1 和多边形所有边的交点。

描述多边形扫描转换的扫描线算法的基本步骤实验目的：实现从多边形顶点表示到点阵表示的转换，从多边形给定的边界出发，通过扫描线的方式求出位于其内部各个像素，从而达到对多边形填充的作用。

算法思想：按扫描线顺序，计算扫描线与多边形的相交的交点，这些交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段，并且二者相间排列。

再用要求的颜色显示这些区间的所有象素。

管用边：指与当前扫描线相交的多边形的边，也称为活线边。

管用边表（AET）：把管用边按与扫描线交点x 坐标递增的顺序存在一个链表中，此链表称为管用边表。

只需对当前扫描线的活动边表作更新，即可得到下一条扫描线的活动边表。

为了方便灵活边表的建立与更新，我们为每一条扫描线建立一个新边表NET，用来存放在该扫描线出现的边。

存储内容为：ymax：边的上端点的y 坐标；x：在ET 中表示边的下端点的x 坐标，在AEL 中则表示边与扫描线的交点的坐标；Δx：边的斜率的倒数；next：指向下一条边的指针。

算法步骤：1、大致确定多边形的范围，进而确定扫描线的范围2、初始化并建立NET 表3、遍历每一条扫描建立ET：对于每一个多边形点，寻找与其构成边的两点，如果寻找到的点在此点的上方（即y0小于y1）,则将此边加入到ET[i]中（i 对应的y0 的坐标）。

这样每次加入的边都是向上，不会重复。

4、置AET 为空；5、执行下列步骤直至NET 和AET 都为空．A.更新。

如ET 中的y 非空，则将其中所有边取出并插入AET 中；B.填充。

对AEL 中的边两两配对，每对边中x 坐标按规则取整，获得管用的填充区段，再填充．C.排序。

如果有新边插入AET，则对AET 中各边排序；D.删除。

将AEL 中满足y=ymax 边删去（因为每条边被看作下闭上开的）E.对AEL 中剩下的每一条边的x 递增Δx，即x = x+Δx;F.将当前扫描线纵坐标y 值递值1；。