图形学（4）多边形的扫描转换（上）由于计算机屏幕的光栅显示，需要发展一套相应的光栅图形学算法配合它。
前面介绍了直线段如何才能显示在计算机屏幕上，接下来要介绍一下多边形如何在计算机屏幕上显示，内部颜色又如何填充。
多边形的扫描转换多边形的扫描转换和区域填充的实质是思考如何在离散的像素集上表示连续的二维图形，目前主要用两种方法表示一个多边形：定点表示和点阵表示定点表示和点阵表示定点表示：用多边形的定点序列来表示多边形，这种方法直观，几何意义强，占内存少，且易于进行几何转换。
但是由于其并未说明具体哪些像素点在多边形内部，故着色时仍需特定算法点阵表示：用多边形内的像素表示多边形，这种方法丢掉了很多多边形的几何属性，不易于几何转换，但却是光栅显示中所需要的表示形式。
定点表示与点阵表示之间的相互转换成了光栅显示中需要研究的重要问题。
其中，定点表示转换为点阵表示称为多边形的扫描转换，而点阵表示转换为定点表示不属于计算机图形学的研究范畴，需要图像识别的知识去实现它。
多边形的扫描转换多边形也有分类：凸多边形（任意两顶点连线均在多边形内），凹多边形（不符合凸多边形的定义），含内环多边形（多边形内包含多边形）现在，要讨论的问题就转化为了已知边界，找到多边形内部的点并填色问题。
X-扫描线算法X-扫描线算法核心思想是按一定顺序，用扫描线去与多边形相交，计算其相交区间并对相交区间填色。
区间的端点通过扫描线与多边形边界线交点获得如图，按y正方向递增的扫描线算法可以按如下步骤求得：确定多边形所需扫描线的最大、最小y值，也即多边形定点的最值。
按y值递增循环，每次循环时循环体中要进行的工作有：a)?扫描线与多边形各边求交b)?所有交点按照递增顺序排序c)?交点配对，确定多边形在该条扫描线处的内、外d)?对“内”区间进行颜色填充但是，这看似没毛病的算法其实是有隐患的，其一就是交点的配对问题。
比如，万一我的扫描线撞上多边形定点，然后多边形与扫描线交点是奇数个怎么办？（也就是上图中过点P3时的情况）X-扫描线算法潜在问题1：交点配对对于交点个数问题，我们只要制定一套严谨的交点个数计数方案，规定好什么时候计算交点，什么时候不计算就行了。
直线光栅化算法1. 概述直线光栅化算法是计算机图形学中常用的一种算法，用于将抽象的直线表示转化为具体的像素点绘制。
通过对直线的各个点进行逐一计算，可以将直线在屏幕上精确地表示出来。
本文将介绍直线光栅化算法的基本原理、具体实现过程以及一些常见优化方法。
2. 直线光栅化算法的原理直线光栅化算法的基本原理是利用数学公式计算直线上各个像素点的坐标，并将其绘制在屏幕上。
直线的坐标由两个点确定，即起点和终点。
下面是直线光栅化算法的基本步骤：2.1 计算斜率与步长首先，根据给定的起点和终点，需要计算直线的斜率和步长。
直线的斜率可以通过以下公式计算：斜率 = (终点的纵坐标 - 起点的纵坐标) / (终点的横坐标 - 起点的横坐标)步长指的是在横坐标上每前进一个单位，纵坐标需要前进多少单位。
步长的计算可以根据直线斜率的正负进行分类讨论。
2.2 根据步长逐点绘制直线在计算了直线的斜率和步长之后，可以按照以下步骤绘制直线：1.初始化当前点的坐标为起点的坐标；2.根据步长的正负，依次对当前点的横坐标和纵坐标进行加减操作，以逐点向终点绘制；3.在每个点的位置上绘制像素。
3. 直线光栅化算法的实现3.1 Bresenham算法Bresenham算法是直线光栅化算法的一种经典实现方式。
它的基本思想是通过递推方式，根据当前点的坐标和斜率来选择下一个像素点的位置。
下面是Bresenham算法的具体实现步骤：1.初始化起点的坐标和终点的坐标；2.计算直线的斜率和步长；3.计算像素点的位置，并绘制像素；4.根据当前点位置和斜率的大小关系，更新下一个像素点的坐标。
Bresenham算法的优点是计算简单，适用于直线斜率大致在0到1之间的情况。
3.2 DDA算法DDA算法是另一种常用的直线光栅化算法，它的基本思想是通过逐点增量的方式来计算直线上的像素点坐标。
下面是DDA算法的具体实现步骤：1.初始化起点的坐标和终点的坐标；2.计算直线的斜率和步长；3.根据步长逐点增量，计算下一个像素点的坐标；4.绘制像素点。
基本图形的光栅化算法如何在指定的输出设备上根据坐标描述构造基本⼆维⼏何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。
图形⽣成的概念图形的⽣成：是在指定的输出设备上，根据坐标描述构造⼆维⼏何图形。
图形的扫描转换：在光栅显⽰器等数字设备上确定⼀个最佳逼近于图形的象素集的过程。
直线段的扫描转换直线的绘制要求（1）直线要直；（2）直线的端点要准确，⽆定向性⽆断裂；（3）直线的亮度、⾊泽要均匀；（4）画线的速度要快；（5）具有不同的⾊泽、亮度、线型等。
解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。
逐点⽐较法：数值微分法(DDA法):增量算法直观、易实现不利于⽤硬件实现x(i+1) = x(i) + 1y(i+1) = y(i) + k中点Bresenhan算法:算法原理：根据直线的斜率确定或选择变量在x或y⽅向上每次递增⼀个单位，⽽另⼀⽅向的增量为1或0，它取决于实际直线与相邻象素点的距离，这⼀距离称为误差项。
中点Bresenham算法——算法步骤输⼊直线的两端点P0(x0,y0)和P1(x1,y1)。
计算初始值△x、△y、D=△x-2△y、x=x0、y=y0。
绘制点(x,y)。
判断D的符号。
若D<0，则(x,y)更新为(x+1,y+1)，D更新为D+2△x-2△y；否则(x,y)更新为(x+1,y), D更新为D-2△y。
当直线没有画完时，重复上⼀步骤，否则结束。
改进的Bresenhan算法——算法步骤1.输⼊直线的两端点P0(x0,y0)和P1(x1,y1)。
2.计算初始值△x、△y、e=-△x、x=x0、y=y0。
3.绘制点(x,y)。
4.e更新为e+2△y，判断e的符号。
若e>0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-2△x；否则(x,y)更新为(x+1,y)。
5.当直线没有画完时，重复步骤3和4。
否则结束。
圆的扫描转换解决的问题：绘出圆⼼在原点，半径为整数R的圆x2+y2=R2。
光栅图形学算法光栅图形学算法基础其二（裁剪算法）光栅图形学算法的研究内容直线段的扫描转换算法多边形的扫描转换与区域填充算法直线裁剪算法反走样算法消隐算法一、裁剪简述使用计算机处理图形信息时，计算机内部存储的图形往往比较大,而屏幕显示的只是图形的一部分。
因此需要确定图形哪些部分落在显示区之内，哪些落在显示区之外。
这个选择的过程就称为裁剪。
常见的裁剪方式有点的裁剪、以及直线段的裁剪。
1、点的裁剪最简单的裁剪方法是把各种图形扫描转换为点之后，再判断点是否在窗口内。
对于任意一点P（x，y），若满足下列两对不等式：则点P在矩形窗口内；否则，点P在矩形窗口之外。
判断图形中每个点是否在窗口内，太费时，一般不可取。
2、直线段的裁剪直线段裁剪算法复杂图形裁剪的基础。
?直线段和剪裁窗口的可能关系：完全落在窗口内完全落在窗口外与窗口边界相交 ?要裁剪一条直线段，首先要判断：（1）它是否完全落在裁剪窗口内？?（2）它是否完全在窗口外？（3）如果不满足以上两个条件，则计算它与一个或多个裁剪边界的交点。
常用的裁剪算法有三种，即Cohen-Sutherland、中点分割法和 Liang-Barsky 裁剪算法。
1） Cohen - Sutherland算法此算法又称编码裁剪算法，算法的基本思想是对每条直线段分三种情况处理：若点p1和p2完全在裁剪窗口内。
“简取”之?若点p1(x1,y1)和p2(x2,y2)均在窗口外，且满足下列四个条件之一：如果直线段既不满足“简取”的条件，也不满足“简弃”的条件？需要对直线段按交点进行分段，分段后判断直线是“简取”还是“简弃”。
每条线段的端点都赋以四位二进制码D3D2D1D0，编码规则如下：若XXleft，则D0=1，否则D0=0若XXright，则D1=1，否则D1=0若yybottom，则 D2=1，否则 D2=0若yytop，则 D3=1，否则 D3=0 窗口及其延长线所构成了9个区域。
