多边形的扫描转换边填充算法

扫描线多边形填充算法扫描线多边形填充算法（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.更新扫描线的位置，继续扫描下一条线段，直至完成对所有边界线的处理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验三多边形的有效边表填充算法一、实验目的与要求1、理解多边形的扫描转换原理、方法；2、掌握有效边表填充算法；3、掌握链表的建立、添加结点、删除节点的基本方法；3、掌握基于链表的排序操作。

二、实验内容在实验二所实现工程的基础上，实现以下内容并把实现函数封装在类CMyGL 中。

1、C++实现有效边表算法进行多边形扫描转换2、利用1进行多边形扫描转换和区域填充的实现；三、实验原理请同学们根据教材及上课的PPT独立完成。

四、实验步骤（程序实现）。

1、建立并选择工程项目。

打开VC6.0->菜单File 的New 项,在projects 属性页选择MFC AppWizard(exe)项，在Project name 中输入一个工程名,如“Sample”。

单文档。

2、新建一个图形类。

选择菜单InsertNew class，Class type 选择“Generic Class”，Name 输入类名，如“CMyCG。

3、向新建的图形类中添加成员函数（实际就是加入实验要求实现的图形生成算法的实现代码）。

在工作区中直接鼠标右键单击，选择“Add Member Function…”项，添加绘制圆的成员函数。

void PolygonFill(int number, CPoint *p, COLORREF color, CDC* pDC)添加其他成员函数：CreatBucket();CreatET();AddEdge();EdgeOrder();4、成员函数的实现。

实现有效边表填充算法。

这一部分需要同学们去实现。

参考实现：多边形的有效边表填充算法的基本过程为：1、定义多边形：2、初始化桶3、建立边表4、多边形填充1)对每一条扫描线，将该扫描线上的边结点插入到临时AET表中，HeadE.2)对临时AET表排序，按照x递增的顺序存放。

3)根据AET表中边表结点的ymax抛弃扫描完的边结点，即ymax>=scanline4)扫描AET表，填充扫描线和多边形相交的区间。

多边形填充算法本在计算机图形学中，使用多边形填充算法可以实现各种图形的绘制，例如：圆形、椭圆形、字母等。

对于任意形状的多边形来说，其内部像素点的坐标是无法直接计算得到的，因此需要通过一定的算法来实现。

常见的多边形填充算法有扫描线填充算法和边界填充算法。

接下来我们来详细了解这两种算法。

扫描线填充算法是通过扫描多边形上的每一条水平线，找到与多边形相交的线段，并进行填充操作。

具体步骤如下：1.找到多边形的最高点和最低点，作为扫描线的起点和终点。

2.将扫描线从起点依次向下移动，直到到达终点。

3.在每一条扫描线上，找到与多边形相交的线段。

4.根据线段的起点和终点，计算交点的x坐标，并从起点到终点对应的像素点进行填充。

5.重复步骤4，直到所有的扫描线都处理完毕。

扫描线填充算法的优点是简单易懂，适用于一般情况。

但是对于复杂的多边形来说，会存在边界交叉的情况，需要特殊处理。

边界填充算法是通过检测多边形的边界点，并进行填充操作。

具体步骤如下：1.找到多边形的最左边、最右边、最上边和最下边的点，作为边界点。

2.从最上边的点开始，依次向下遍历每一行像素点。

3.在每一行中，寻找与多边形边界相交的点，并进行填充操作。

4.重复步骤3，直到到达最下边的点。

边界填充算法的优点是对具有复杂交叉边界的多边形也能进行正确的填充操作。

但是对于非凸多边形来说，边界填充算法可能会有空隙出现。

除了以上两种常见的多边形填充算法，还有其他一些算法也可以实现多边形的填充操作，例如：扫描转换填充算法、边界边框填充算法等。

在实际应用中，多边形填充算法通常结合图形处理库或者计算机图形学软件来实现。

这些软件提供了丰富的函数和方法，可以直接调用进行多边形的填充操作。

综上所述，多边形填充算法是计算机图形学中的一个重要算法。

通过扫描线填充算法或者边界填充算法，可以实现对任意形状多边形的填充操作。

随着计算机图形学的发展，多边形填充算法也不断进化和优化，以满足不同应用场景的需求。

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

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

如何具体实现（如何找到入点、出点）？根据区域的连贯性，分为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指针：同边表。

实验六扫描线填充算法一、实验目的编写多边形的扫描线填充算法程序，加深对扫描线算法的理解，验证算法的正确性。

二、实验任务（2学时）编写多边形的扫描线填充算法程序，利用数组实现AET，考虑与链表实现程序的不同。

三、实验内容1、算法对一条扫描线的填充一般分为以下4个步骤：（1）求交：计算扫描线与多边形各边的交点；（2）排序：把扫描线上所有交点按递增顺序进行排序；（3）配对：将第一个交点与第二个交点，第三个交点与第四个交点等等进行配对，每对交点代表扫描线与多边形的一个相交区间。

（4）着色：把区间内的像素置为填充色。

2、成员函数的关系主程序名为fill_area(count, x, y)，其中参数x, y是两个一维数组，存放多边形顶点（共c ount个）的x和y坐标。

它调用8个子程序，彼此之间的调用关系图1所示为：图1 fill_area的程序结构3、算法的程序设计步骤1：创建“S_L_Fill”工程文件；步骤2：创建类class：“EACH_ENTRY”。

在工作区“S_L_Fill classes”单击右键-→“new class”-→选择类型“Generic Class”名称为“EACH_ENTRY”，添加成员变量（添加至“class EACH_ENTRY { public:”之内）：int y_top;float x_int;int delta_y;float x_change_per_scan;步骤3：包含头文件，同时初始化定义多边形顶点数目。

在“class CS_L_FillView : public Cview……”之前添加代码“#include EACH_ENTRY.h”及“#define MAX_POINT 9”。

#define MAX_POINT 9#include "EACH_ENTRY.h"步骤4：在类“class CS_L_FillView”中添加成员变量（鼠标双击工作区“CS_L_FillView”，代码添加至“class CS_L_FillView : public Cview {protected: ……public:之后”）：EACH_ENTRY sides[MAX_POINT];int x[MAX_POINT],y[MAX_POINT];int side_count,first_s,last_s,scan,bottomscan,x_int_count;步骤5：利用构造函数“CS_L_FillView::CS_L_FillView()”初始化顶点坐标（鼠标双击工作区“CS_L_FillView”，代码添加至“CS_L_FillView（）之内”）：x[0]=200;y[0]=100;x[1]=240;y[1]=160;x[2]=220;y[2]=340;x[3]=330;y[3]=100;x[4]=400;y[4]=180;x[5]=300;y[5]=400;x[6]=170;y[6]=380;x[7]=120;y[7]=440;x[8]=100;y[8]=220;步骤6：在“class CS_L_FillView”下添加实现不同功能的成员函数。

计算机科学与技术学院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所示。

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

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

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

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

管用边表（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；。

多边形区域填充算法－－扫描线填充算法（有序边表法）有代码⼆、扫描线算法（Scan-Line Filling）转载 https:///u013044116/article/details/49737585扫描线算法适合对⽮量图形进⾏区域填充，只需要直到多边形区域的⼏何位置，不需要指定种⼦点，适合计算机⾃动进⾏图形处理的场合使⽤，⽐如电脑游戏和三维CAD软件的渲染等等。

对⽮量多边形区域填充，算法核⼼还是求交。

⼀⽂给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利⽤此算法可以判断⼀个点是否在多边形内，也就是是否需要填充，但是实际⼯程中使⽤的填充算法都是只使⽤求交的思想，并不直接使⽤这种求交算法。

究其原因，除了算法效率问题之外，还存在⼀个光栅图形设备和⽮量之间的转换问题。

⽐如某个点位于⾮常靠近边界的临界位置，⽤⽮量算法判断这个点应该是在多边形内，但是光栅化后，这个点在光栅图形设备上看就有可能是在多边形外边（⽮量点没有⼤⼩概念，光栅图形设备的点有⼤⼩概念），因此，适⽤于⽮量图形的填充算法必须适应光栅图形设备。

2.1扫描线算法的基本思想扫描线填充算法的基本思想是：⽤⽔平扫描线从上到下（或从下到上）扫描由多条⾸尾相连的线段构成的多边形，每根扫描线与多边形的某些边产⽣⼀系列交点。

将这些交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜⾊画⽔平直线。

多边形被扫描完毕后，颜⾊填充也就完成了。

扫描线填充算法也可以归纳为以下4个步骤：（1）求交，计算扫描线与多边形的交点（2）交点排序，对第2步得到的交点按照x值从⼩到⼤进⾏排序；（3）颜⾊填充，对排序后的交点两两组成⼀个⽔平线段，以画线段的⽅式进⾏颜⾊填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第1步继续处理；整个算法的关键是第1步，需要⽤尽量少的计算量求出交点，还要考虑交点是线段端点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显⽰。