直线反走样算法

A. 计算机图形学复习

第一章
1. 计算机图形：用数学方法描述，通过计算机生成、处理、存储和显示的对象。
2. 图形和图像的主要区别是表示方法不同：图形是用矢量表示；图像是用点阵表示的。图形和图像也可以通过光栅显示器（或经过识别处理）可相互转化。
3. 于计算机图形学紧密相关的学科主要包括 图像处理、计算几何和计算机视觉模式识别。它们的共同点是 以图形/图像在计算机中的表示方法为基础。
4. 交互式计算机图形系统的发展可概括为以下4个阶段：字符、矢量、二维光栅图形、三维图形。
5. 图形学研究的主要内容有：①几何造型技术 ②图形生成技术 ③图形处理技术 ④图形信息的存储、检索与交换技术 ⑤人机交互技术 ⑥动画技术 ⑦图形输入输出技术 ⑧图形标准与图形软件包的研发。
6. 计算机辅助设计和计算机辅助制造 是计算机图形学最广泛最活跃的应用领域。
7. 计算机图形学的基本任务：一是如何利用计算机硬件来实现图形处理功能；二是如何利用好的图形软件；三是如何利用数学方法及算法解决实际应用中的图行处理问题。
8. 计算机图形系统是由硬件系统和软件系统组成的。
9. 计算机图形系统包括处理、存储、交互、输入和输出五种基本功能。
10. 键盘和鼠标是最常用的图形输入设备。鼠标根据测量位移部件的不同，分为光电式、光机式和机械式3种。
11. 数字化仪分为电子式、超声波式、磁伸缩式、电磁感应式等。小型的数字化仪也称为图形输入板。
12. 触摸屏是一种 定位设备，它是一种对于触摸能产生反应的屏幕。
13. 扫描仪由3部分组成：扫描头、控制电路和移动扫描机构。扫描头由光源发射和光鲜接收组成。按移动机构的不同，扫描仪可分为平板式和滚筒式2种。
14. 显示器是计算机的标准输出设备。彩色CRT的显示技术有2种：电子穿透法和荫罩法。
15. 随机扫描是指电子束的定位及偏转具有随意性，电子束根据需要可以在荧光屏任意方向上连续扫描，没有固定扫描线和扫描顺序限制。它具有局部修改性和动态性能。
16. 光栅扫描显示器是画点设备。
17. 点距是指相邻像素点间的距离，与分辨指标相关。
18. 等离子显示器一般有三层玻璃板组成，通常称为等离子显示器的三层结构。
19. 用以输出图形的计算机外部设备称为硬拷贝设备。
20. 打印机是廉价的硬拷贝设备，从机械动作上常为撞击式和非撞击式2种。
21. 常用的喷墨头有：压电式、气泡式、静电式、固体式。
22. 绘图仪分为静电绘图仪和笔式绘图仪。
23. 图形软件的分层。由下到上分别是：①图形设备指令、命令集、计算机操作系统 ②零级图形软件 ③一级图形软件 ④二级图形软件 ⑤三级图形软件。
24. 零级图形软件是面向系统的、最底层的软件，主要解决图形设备与主机的通信与接口问题，又称设备驱动程序。
25. 一级图形软件即面向系统又面向用户，又称基本子系统。
26. 图形应用软件是系统的核心部分。
27. 从物理学角度，颜色以主波长、色纯度和辉度来描述；从视觉角度来看，颜色以色彩、饱和度和亮度来描述。
28. 用适当比列的3种颜色混合，可以获得白色，而且这3种颜色中的任意2种的组合都不能生成第三种颜色，称为三原色理论。
29. RGB模型的匹配表达式是：c=rR+gG+bB。
30. 常用颜色模型
颜色模型名称 使用范围
RGB 图形显示设备（彩色CRT和光栅显示器）
CMY 图形打印、绘制设备
HSV 对应画家本色原理、直观的颜色描述
HSL 基于颜色参数的模型
用基色青、品红、黄定义的CMY颜色模型用来描述硬拷贝设备的输出颜色。它从白光中滤去某种颜色，故称为减色性原色系统。

第二章
31. 直线生成的3个常用算法：数值微分法（DDA）、中点划线法和Bresenham算法。
32. DDA算法的C语言实现：
DDA算法生成直线，起点（x0,y0）,终点（x1,y1）.
Void CMy View ::OnDdaline()
{
CDC *pDC=GetDC(); //获得设备指针
int x0=100,y0=100,x1=300,y1=200,c=RGB(250,0,0);//定义直线两端点和直线颜色
int x,y,i;
float dx,dy,k;
dx=(float)(x1-x0);
dy=(float)(y1-y0);
k=dy/dx;
x=x0;
y=y0;
if(abs(k)<1)
{ for(;x<=x1;x++)
{pDC—>SetPixel(x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{ for(;y<=y1;y++)
{pDC—>SetPixel(int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC); //释放设备指针
}
33. 任何影响图元显示方法的参数称为属性参数。图元的基本表现是线段，其基本属性包括线型、线宽和色彩。
34. 最常见的线型包括实线、虚线、细线和点划线等，通常默认的线型是实线。
35. 线宽控制的实线方法：垂直线刷子、水平线刷子、方形线刷子。生成具有宽度的线条还可以采用区域填充算法。
36. 用离散量表示连续量时引起的失真现象称为走样。为了提高图形显示质量，减少或消除走样现象的技术称为反走样。
37. 反走样技术有：提高分辨率（硬件方法和软件方法）、简单区域取样、加权区域取样。
38. 区域连通情况分为四连通区域和八连通区域。四连通区域是指从区域上某一点出发，可通过上下左右4个方向移动，在不越出区域的前提下到达区域内的任意像素；八连通区域是指从区域内某一像素出发，可通过上下左右、左上左下、右上右下8个方向的移动，在不越出区域的前提下到达区域内的任意像素。
39. 字符的图形表示可以分为点阵式和矢量式两种形式。
40. 在图形软件中，除了要求能生成直线、圆等基本图形元素外，还要求能生成其他曲线图元、多边形及符号等多种图元。
41. 在扫描线填充算法中，对水平边忽略而不予处理的原因是实际处理时不计其交点。
42. 关于直线生成算法的叙述中，正确的是：Bresenham算法是对中点画线算法的改进。
43. 在中点画圆算法中叙述错误的是：为了减轻画圆的工作量，中点画圆利用了圆的四对称性性质。
44. 多边形填充时，下列论述错误的是：在判断点是否在多边形内时，一般通过在多变形外找一点，然后根据该线段与多边形的交点数目为偶数即可认为在多边形内部，若为奇数则在多边形外部，且不考虑任何特殊情况。
第三章
1. Cohen-Sutherland算法，也称编码裁剪法。其基本思想是：对于每条待裁剪的线段P1P2分三种情况处理：①若P1P2完全在窗口内，则显示该线段，简称“取”之；②若P1P2完全在窗口外，则丢弃该线段，简称“舍”之；③若线段既不满足“取”的条件也不满足“舍”的条件，则求线段与窗口边界的交点，在交点处把线段分为两段，其中一段 完全在窗口外，可舍弃之，然后对另一段重复上述处理。
2. Sutherland-Hodgman算法，又称逐边裁剪算法。其基本思想是用窗口的四条边所在的直线依次来裁剪多边形。多边形的每条边与裁剪线的位置关系有4种情况（假设当前处理的多边形的边为SP）：a>端点S在外侧，P在内侧，则从外到内输出P和I；b>端点S和P都在内侧，则从内到内输出P；c>端点S在内侧，而P在外侧，则从内到外输出I；d>端点S和P都在外侧，无输出。
3. 按裁剪精度的不同，字符裁剪可分为三种情况：字符串裁剪、字符裁剪和笔画裁剪。
4. 在线段AB的编码裁剪算法中，如A、B两点的码逻辑或运算全为0，则该线段位于窗口内；如AB两点的码逻辑与运算结果不为0，则该线段在窗口外。
5. n边多边形关于矩形窗口进行裁剪，结果多边形最多有2n个顶点，最少有n个顶点。
6. 对一条等长的直线段裁剪，编码裁剪算法的速度和中点分割算法的裁剪速度哪一个快，无法确定。（√）
7. 多边形裁剪可以看做是线段裁剪的组合。（X）
8. 对于线段来说，中点分割算法要比其他线段裁剪算法的裁剪速度快。（X）
9. 多边形的Weiler-Atherton裁剪算法可以实现对任意多边形的裁剪。（√）
第四章
1. 几何变换是指改变几何形状和位置，非几何变换是指改变图形的颜色、线型等属性。变换方法有对象变换（坐标系不动）和坐标变换（坐标系变化）两种。
2. 坐标系可以分为以下几种：世界坐标系（是对计算机图形场景中所有图形对象的空间定位和定义，是其他坐标系的参照）、模型坐标系（用于设计物体的局部坐标系）、用户坐标系(为了方便交互绘图操作，可以变换角度、方向)、设备坐标系（是绘制或输出图形的设备所用的坐标系，采用左手系统）。
3. 将用户坐标系中需要进行观察和处理的一个坐标区域称为窗口，将窗口映射到显示设备上的坐标区域称为视区。从窗口到视区的变换，称为规格化变换。（eg.4-1）
4. 所谓体素，是指可以用有限个尺寸参数定位和定形的体，如长方体、圆锥体。
5. 所谓齐次坐标表示，就是用n+1维向量表示n维的向量。
6. 二维点（x,y）的齐次坐标可以表示为：（hx hy h）,其中h≠0。当h=1时称为规范化的齐次坐标，它能保证点集表示的唯一性。
7. 旋转变换公式的推导、对称变换

第五章
1. 交互绘图技术是一种处理用户输入图形数据的技术，是设计交互绘图系统的基础。常见的交互绘图技术有：定位技术、橡皮筋技术、拖曳技术、定值技术、拾取技术、网格与吸附技术。
2. 常用的橡皮筋技术有：橡皮筋直线、橡皮筋矩形、橡皮筋圆。
3. 拖曳技术是将形体在空间移动的过程动态地、连续地表示出来，直到用户满意。
4. 定值技术有2种：一种是键入数值，另一种是改变电位计阻值产生要求的数量，可以用模拟的方式实现电位计功能。
5. 拾取一个基本的对象可以通过：指定名称法、特征点发、外界矩阵法、分类法、直接法。

第六章
1. 点、线、面是形成三维图形的基础，三维变换是从点开始。
2. 三维图形变换分类：三维图形变换包括三维几何变换和平面几何变换，三维几何变换包括基本几何变换和复合变换；平面几何变换包括平行投影和透视投影，平行投影包括正投影和轴测投影，透视投影包括一点透视、二点透视、三点透视。
3. 投影中心与投影面之间的距离是无限的投影叫做平行投影，它包括正投影和轴测投影。
4. 正投影形成的视图包括：主视图、俯视图和左视图。轴测投影形成的视图为轴测图。
5. 透视投影也称为中心投影，其投影中心与投影面之间的距离是有限的。其特点是产生近大远小的视觉效果
6. 对于透视投影，不平行于投影面的平行线的投影会汇聚到一个点，这个点称为灭点。透视投影的灭点有无限多个，与坐标轴平行的平行线在投影面上形成的灭点称为主灭点。主灭点最多有3个，其对应的透视投影分别称为一点透视、二点透视、三点透视。

第七章
1. 型值点是曲面或曲线上的点，而控制点不一定在曲线曲面上，控制点的主要目的是用来控制曲线曲面的形状。
2. 插值和逼近是曲线曲面设计中的两种不同方法。插值—生成的曲线曲面经过每一个型值点，逼近—生成的曲线曲面靠近每一个控制点。
3. 曲线曲面的表示要求：唯一性、统一性、几何不变性、几何直观、易于界定、易于光滑连接。
4. 曲线曲面有参数和非参数表示，但参数表示较好。非参数表示又分为显式和隐式两种。
5. 对于一个平面曲线，显式表示的一般形式是：y=f(x)。一个x与一个y对应，因此显式方程不能表示封闭或多值曲线。例不能用显式方程表示一个圆。
6. 如果一个曲线方程表示为f(x,y)=0的形式，我们称之为隐式表示。其优点是易于判断函数f(x,y)是否大于、小于或等于零，即易于判断是落在所表示曲线上还是在曲线的哪一侧。
7. 参数连续与几何连续的区别：参数连续性是传统意义上的、严格的连续，而几何连续性只需限定两个曲线段在交点处的参数导数成比例，不必完全相等，是一种更直观、易于交互控制的连续性。
8. 在曲线曲面造型中，一般只用到C1（1阶参数连续）、C2（2阶参数连续）、G1（1阶几何连续）、G2（2阶几何连续）。切矢量（一阶导数）反映了曲线对参数t的变化速递，曲率（二阶导数）反映了曲线对参数t变化的加速度。
9. 通常C1连续必能保证G1的连续，但G1的连续并不能保证C1连续。
10. 对于三次Hermite曲线，用于描述曲线的可供选择的条件有：端点坐标、切矢量和曲率。
11. 三次Hermite曲线特点：①可局部调整，因为每个曲线段仅依赖于端点约束；②基于Hermite样条的变化形式有Cardinal样条和Kochanek-Bartels样条；③具有几何不变性。
12. Bezier曲线的性质：①端点性质②端点切矢量③端点的曲率④对称性⑤几何不变性⑥凸包性⑦变差缩减性。
13. 一次Bezier曲线是连接起点P0和终点P1的直线段，二次Bezier曲线对应一条起点P0终点在P2处的抛物线。
14. B样条曲线的性质：①局部性②连续性或可微性③几何不变性④严格凸包性⑤近似性⑥变差缩减性。
15. NURRS曲线具有以下性质：①局部性②可微性③仿射不变性④严格保凸性⑤一般性⑥变差缩减性⑦端点性质。

第八章
1. 要把三维物体的信息显示在二维显示设备中，必须通过投影变换。由于投影变换失去了深度信息，往往会导致二义性，要消除二义性，就必须在绘制时消除实际不可见的线和面，称作消除隐藏线和隐藏面，简称消隐。
2. 面消隐常用算法有：深度缓冲区（Z-buffer）算法和深度排序算法（画家算法）。
3. 深度缓冲区算法和深度排序算法的区别：

B. 学习计算机图形学的书籍介绍

目录

计算机图形学基础教程（Visual C++版）

第1章 导论1
1.1 计算机图形学的应用领域1
1.1.1 计算机辅助设计1
1.1.2 计算机艺术1
1.1.3 虚拟现实3
1.1.4 计算机辅助教学3
1.2 计算机图形学的概念4
1.3 计算机图形学的相关学科5
1.4 计算机图形学的确立和发展5
1.5 图形显示器的发展及其工作原理7
1.5.1 阴极射线管7
1.5.2 随机扫描显示器8
1.5.3 直视储存管显示器8
1.5.4 光栅扫描显示器9
1.5.5 液晶显示器13
1.5.6 等离子显示器15
1.5.7 三维显示器15
1.6 图形软件标准的形成18
1.7 计算机图形学的最新技术18
1.7.1 交互技术18
1.7.2 造型技术18
1.7.3 真实感图形显示技术19
1.8 小结19
习题119第2章 Visual C++6.0绘图基础21
2.1 面向对象程序设计基础21
2.1.1 类和对象21
2.1.2 构造函数和析构函数22
2.1.3 对象的动态建立和释放24
2.1.4 继承与派生25
2.2 MFC上机操作步骤28
2.3 基本绘图函数31
2.3.1 CDC类结构和GDI对象32
2.3.2 映射模式33
2.3.3 CDC类的主要绘图成员函数34
2.3.4 设备上下文的调用和释放50
2.3.5 VC++绘制图形的几种方法51
2.4 小结52
习题252第3章 基本图形的扫描转换55
3.1 直线的扫描转换55
3.1.1 算法原理56
3.1.2 构造中点偏差判别式56
3.1.3 递推公式57
3.2 圆的扫描转换57
3.2.1 算法原理58
3.2.2 构造中点偏差判别式59
3.2.3 递推公式60
3.3 椭圆的扫描转换60
3.3.1 算法原理61
3.3.2 构造上半部分I中点偏差判别式62
3.3.3 上半部分I的递推公式62
3.3.4 构造下半部分II中点偏差判别式64
3.3.5 下半部分II的递推公式64
3.4 反走样技术66
3.5 直线距离加权反走样算法67
3.5.1 算法原理67
3.5.2 构造距离判别式69
3.5.3 计算机化69
3.6 小结69
习题369第4章 多边形填充72
4.1 实面积图形的概念72
4.1.1 多边形的定义73
4.1.2 多边形的表示73
4.1.3 多边形的填充74
4.1.4 区域填充74
4.2 有效边表填充算法75
4.2.1 填充原理75
4.2.2 边界像素的处理原则75
4.2.3 有效边和有效边表76
4.2.4 边表79
4.3 边缘填充算法80
4.3.1 填充原理80
4.3.2 填充过程80
4.4 区域填充算法82
4.4.1 填充原理82
4.4.2 四邻接点和八邻接点82
4.4.3 四连通域和八连通域83
4.4.4 四邻接点填充算法和八邻接点填充算法84
4.5 小结85
习题485第5章 二维变换和裁剪89
5.1 图形几何变换基础89
5.1.1 规范化齐次坐标89
5.1.2 矩阵相乘89
5.1.3 二维变换矩阵90
5.1.4 二维几何变换90
5.2 二维图形基本几何变换矩阵91
5.2.1 平移变换矩阵91
5.2.2 比例变换矩阵91
5.2.3 旋转变换矩阵92
5.2.4 反射变换矩阵93
5.2.5 错切变换矩阵94
5.3 二维复合变换95
5.3.1 复合变换原理95
5.3.2 相对于任一参考点的二维几何变换95
5.3.3 相对于任意方向的二维几何变换96
5.4 二维图形裁剪98
5.4.1 图形学中常用的坐标系98
5.4.2 窗口和视区及窗视变换99
5.4.3 窗视变换矩阵100
5.5 Cohen-Sutherland直线裁剪算法101
5.5.1 编码原理101
5.5.2 裁剪步骤102
5.5.3 交点计算公式102
5.6 中点分割直线裁剪算法103
5.6.1 中点分割直线裁剪算法原理103
5.6.2 中点计算公式103
5.7 梁友栋-Barsky直线裁剪算法103
5.7.1 梁友栋算法原理103
5.7.2 算法分析104
5.7.3 算法的几何意义104
5.8 小结106
习题5106第6章 三维变换和投影108
6.1 三维几何变换108
6.1.1 三维变换矩阵108
6.1.2 三维几何变换108
6.2 三维基本几何变换矩阵109
6.2.1 平移变换109
6.2.2 比例变换109
6.2.3 旋转变换110
6.2.4 反射变换111
6.2.5 错切变换112
6.3 三维复合变换113
6.4 投影变换115
6.4.1 三视图115
6.4.2 斜等侧图118
6.5 透视变换120
6.5.1 透视变换坐标系120
6.5.2 坐标系变换121
6.5.3 用户坐标系到观察坐标系的变换122
6.5.4 观察坐标系到屏幕坐标系的变换124
6.5.5 透视投影分类125
6.6 小结127
习题6128第7章 自由曲线和曲面130
7.1 基本概念130
7.1.1 样条曲线曲面130
7.1.2 曲线曲面的表示形式130
7.1.3 拟合和逼近131
7.1.4 连续性条件131
7.2 三次参数样条曲线132
7.2.1 参数样条曲线定义132
7.2.2 系数求解133
7.2.3 边界条件133
7.3 Hermite样条曲线135
7.4 Bezier曲线137
7.4.1 Bezier曲线的定义137
7.4.2 Bezier曲线的性质139
7.4.3 Bezier曲线的可分割性139
7.5 Bezier曲面141
7.5.1 Bezier曲面的定义141
7.5.2 双三次Bezier曲面的定义141
7.6 B样条曲线142
7.6.1 B样条曲线的定义143
7.6.2 二次B样条曲线143
7.6.3 三次B样条曲线144
7.6.4 B样条曲线的性质146
7.6.5 构造特殊的三次B样条曲线的技巧148
7.7 B样条曲面149
7.7.1 B样条曲面的定义149
7.7.2 双三次B样条曲面的定义149
7.7.3 双三次B样条曲面的连续性150
7.8 小结152
习题7152第8章 分形几何156
8.1 分形和分维156
8.1.1 分形的诞生156
8.1.2 分形的基本特征157
8.1.3 分形的定义158
8.1.4 分形维数的定义158
8.2 递归模型160
8.2.1 Cantor集160
8.2.2 Koch曲线161
8.2.3 Peano-Hilbert曲线162
8.2.4 Sierpinski垫片、地毯和海绵164
8.2.5 C字曲线168
8.2.6 Caley树168
8.3 L系统模型169
8.3.1 L系统文法169
8.3.2 Koch曲线170
8.3.3 分形草171
8.3.4 Peano-Hilbert曲线171
8.3.5 分形灌木丛173
8.4 IFS迭代函数系统模型174
8.4.1 仿射变换174
8.4.2 IFS175
8.4.3 Koch曲线178
8.4.4 Sierpinski垫片180
8.4.5 枫叶生成182
8.5 小结183
习题8183第9章 动态消隐187
9.1 图形的数据结构187
9.1.1 图形的几何信息和拓扑信息187
9.1.2 基本图形的数据结构187
9.1.3 立体表示模型188
9.2 消隐算法分类190
9.3 隐线算法190
9.3.1 凸多面体消隐算法190
9.3.2 曲面体消隐算法192
9.4 隐面算法194
9.4.1 Z-Buffer算法194
9.4.2 画家算法197
9.5 小结198
习题9198第10章 真实感图形201
10.1 颜色模型201
10.1.1 基本概念201
10.1.2 RGB颜色模型202
10.1.3 Gouraud颜色渐变203
10.2 材质模型和光照模型205
10.2.1 物体的材质205
10.2.2 环境光模型206
10.2.3 漫反射光模型206
10.2.4 镜面反射光模型207
10.2.5 光强的衰减208
10.3 纹理映射209
10.3.1 纹理定义209
10.3.2 纹理映射210
10.4 OpenGL简介210
10.4.1 案例效果210
10.4.2 TestView.h文件210
10.4.3 TestView.cpp文件213
10.4.4 程序说明220
10.5 小结222
习题10222附录A 配套实践教程的案例设置及与本书的对应关系225

C. 走样直线和反走样直线的区别

1. 反走样是用于减少或消除这种效果的技术。简介在光栅图形显示器上绘制非水平且非垂直的直线或多边形边界时，或多或少会呈现锯齿状或台阶状外观。

2. .一条恰当的直线看上去应该是什么样的?直线有多粗?尾端应该是怎么样的?直线是一个一维物体,无限长.它没有什么粗细.

D. 系统框图如下 java实现五子棋程序 可以实现人人对战 人机对战 简单功能 悔棋 认输

一、实验题目

五子棋游戏。

二、问题分析

五子棋是双人博弈棋类益智游戏，由围棋演变而来，属纯策略型。棋盘通常15*15，即15行，15列，共225个交叉点，即棋子落点；棋子由黑白两色组成，黑棋123颗，白棋122颗。游戏规则为黑先白后，谁先五子连成一条直线谁赢，其中直线可以是横的、纵的、45度、135度。

本次Java编程我的目的是现实人机对战，即游戏者一方是人，另一方计算机。这就要求程序不仅要具备五子棋的基本界面，还要编程指导计算机与人进行对弈。为了使程序尽可能智能，我采用了贪心策略、传统搜索算法、极大极小博弈树算法，对应游戏玩家的3个等级：简单、中等、困难。

三、功能设计

我的程序基本功能是实现人机对弈五子棋。人和电脑交替下棋，谁先五子连成一条直线谁就赢。下面是我程序的功能模块：

1.等级设置

核心功能是实现不同策略与算法的对比运用，纯贪心策略实现简单等级对手，直接搜索算法实现中等等级对手，极大极小博弈树算法实现困难等级对手。对应程序中的3选1单选按钮。

2.悔棋功能

模拟栈机制实现人悔棋，不限步长的悔棋。对应程序中的悔棋按钮。

3.棋面绘制

根据不同机计算机的屏幕分辨率，绘制逼真的棋盘。

4.图片引入

两张古典的人物图片，生动模拟对弈双方。人物图片旁的黑白棋钵图片显示黑白棋归属。

5.背景设置

支持用户选择背景，包括棋盘、棋盘边框、窗口边框，彰显个性。

6.音乐播放

下棋时有棋子落地的声音，一方胜利时有五子连成一片的声音。同时在设置背景时相应的改变整个对弈过程中的背景音乐。

7.时间显示

在棋盘正上方有一模拟文本框显示当前棋局用时。

8.其他小功能

支持和棋、认输、开启新游戏、退出游戏等操作。

四、数据结构与算法设计

数据结构部分

1.当前棋局的存储结构

我的五子棋程序选择通常用到的15行*15列棋盘，可以开二维数组PositionFlag=newint[15][15]，PositionFlag[i][j]为0表示(i,j)点尚无棋，为1表示(i,j)点是人的棋子，为2表示(i,j)点是机器的棋子。之所以选择二维数组，主要原因有两点：

1.本程序需要频繁随机访问15*15的交叉点，对应查询该点状态以及改变该点状态，随机访问是数组的特点。

2.15*15=225开二维数组的内存需求相对现在内存为2G及以上的计算机完全可以接受，且数组实现简单、操作方便。

基于以上两点，尽管创建动态的顺序表—链表可能可以节省少量内存（可以只存当前有棋的点，原数组对应位置为0的点可以不存），但选择数组的优势完全在上述两点体现了出来。

2.实现悔棋操作的数据结构

由于每次悔棋只需回退当前几步，后进先出原则，这正是栈这种典型数据结构的设计思想，于是我选择栈。我自己先写了用自定义数组模拟的栈，但由于是学Java语言且由于悔棋的存储空间需要随当前步数增大而增大（由于每局最多下225步，即最多要悔225步，所以自己开个225的数组完全可以避免存储空间自增长的问题且内存完全可以接受，之所以不用自定义数组而用ArrayList类主要是为了尝试Java中STL的用法），所有我最终改为用Java类库中的ArrayList类。

确定用ArrayList类实现栈机制后就必须考虑每个ArrayList单元具体存储什么。刚开始我存储的是当前的棋局，即整个局面，而每个局面对应一个二维数组，这样是很占用内存的。试想一下，在最坏情况下，225个ArrayList单元，每个单元存放一个15*15的二维数组，尽管225*15*15在Java的内存管理机制下不会爆栈，但也是极不划算的。之所以说不划算，是因为有更好的解决方案。由于每次悔棋只是在回退倒数一步，多步悔棋只需循环回退，所以可以只存储当前棋局最后一步的下法，对应一个二维点，完全可以自定义一个二维坐标类chessOneStep。

算法设计部分

Java语言是面向对象的语言。我在进行五子棋游戏编程是总共传创建了11个自定义的类。在编写程序的过程中，我有一个明显的体验就是面向对象编程就是一项有关对象设计和对象接口技术，很多关键的技术就是如何设计自定义的对象。

下面我先概括给出我的所有类的作用：

1.mainFrame类：主框架类，我应用程序的入口；

2.chessPositon类：主控类，这个类是我程序的核心类，负责控制双方的下棋，以及调用其他的类完成当前棋局的显示绘制；

3.chessPanel类：面板类，调用其他底层类完成当前棋局的显示绘制；

4.chessBoard类：棋盘绘制类，负责棋盘的绘制；

5.chessImage类：文件类，包含各种资源（背景图片、背景音乐）以及静态全局变量（publicstaticType）；

6.chessButton类：组件类，定义各种组件，包括按钮、单选按钮、文本框等；

7.chessMusic类：音乐类，负责调用Java库类完成背景音乐、下棋音乐、取胜音乐等的播放；

8.chessPiece类：棋局类，定义棋局二维数组数据结构并完成相关操作；

9.chessList类：栈类，完成悔棋等操作；

10.chessOneStep类：棋子类，定义每步坐标以及下在该处获得的估价值；

11.myCompare类：排序类，完成chessOneStep类的自定义排序

详细设计

1.mainFrame类

作为我的五子棋程序的主类，mainFrame类主要实例化相关的对象，如chessbutton,chessborad等，从而完成框架的创建。更重要的是实例化chessposition，这是本程序的核心类，控制游戏双方行棋过程完成人机互动下棋，然后将MyChessPosition与鼠标响应addMouseListener（）关联起来。

2.chessMusic类

一个好的游戏必须给人一种身临其境的感觉，而声音是营造这种氛围的重要因素。参照网上各游戏运行商的音乐配置，我选择相关逼真的声音。包括背景音乐、下棋棋子落到棋盘发出的声音以及一方胜出的配乐。所有这些功能的实现，依赖于自定义的chessMusic类，采用AudioInputStream配合Clip的方式完成音乐播放的软硬件工作，然后定义两个接口chessmusic(StringName)和Stop(),前者完成播放功能，后者完成关闭当前音乐功能。因为音频文件相对较大，而我的程序提供在不同背景乐之间切换的功能，所以在打开另一个音频文件之前必须关闭前一个正在播放的音频文件，防止出现溢出。

3.chessImage类

适当的动画或图片能给游戏玩家带来美的体验。所以我的五子棋程序界面在不失和谐的前提下引入了尽可能多的图片，包括对弈双方、棋钵等。图片引入的具体工作通过语句importjavax.imageio.ImageIO完成。同时，由于图片要在用到它的类中被访问，为了避免频繁调用函数，我直接将图片相关联的对象定义为publicstatic，表明是公用的、静态的。进一步引申开去，我将程序中用到的静态全局变量都定义在chessImage类中。具体如下：

publicstaticDatebegin;//每局开始时间

publicstaticDatecur;//每局结束时间

;//结束端点1

;//结束端点2

publicstaticbooleanIsGameOver;//是否只有一方获胜

[][]={{255,227,132},{0,255,127},{218,165,32}};//背景颜色

publicstaticintColorOfWindows[][]={{60,179,113},{245,245,245},{122,122,122}};//背景颜色

publicstaticintWitchMatch;//背景搭配

;//背景音乐

publicstaticintCurrentStep;//记录当前步数

publicstaticintRank;//设置难度等级

;//判断是否认输

publicstaticbooleanIsTie;//判断是否认输

publicstaticStringMessage;//输出提示信息

publicstaticImageIconImage;//图标

publicstaticImageblackBoard;//白棋盘

publicstaticImagewhiteBoard;//黑棋盘

publicstaticImageblackChess;//白棋棋子图片

publicstaticImagewhiteChess;//白棋棋子图片

publicstaticImageRightPlayer;//白棋棋罐图片

publicstaticImageLeftPlayer;//白棋玩家头像图片

publicstaticStringpath="src/";//图片的保存路径

4.chessButton类

这个是程序的组件类。定义了各种功能键，完善程序功能，营造逼真的人机对战游戏效果。分为3类：效果。。

(1)、按钮组件

本程序有5个按钮，支持和棋、认输、新游戏、退出、悔棋等。认输和和棋按钮终止当前的棋局，给出相应的提示信息；退出按钮调用系统System.exit(0)的函数正常返回；悔棋按钮调用后面要介绍的chessList类实现悔棋；新游戏按钮则刷新当前棋局准备下一轮，要将记录当前棋局的二维数组全部置0，刷新当前棋局开始时间等。

(2)、单选按钮组件

游戏界面支持设置个性化界面，包括背景颜色与背景音乐，跟重要的一点是设置难度（简单、中等、困难）。单选按钮只能多选一。背景颜色主要是存储相关颜色搭配方案的RGB颜色，开2维数组，即对应RGB3原色数组的一维数组，然后通过改变WitchMatch全局变量的值来有用户自己选择颜色搭配，不同的颜色搭配对应不同的背景音乐表达一致的主题。难度设置主要是改变计算机的下棋算法，不同难度通过Rank判断进入不同的程序分支，实现不同智能等级的计算机下棋水平。

(3)、文本框

在不同的单选按钮前添加相应的文本框，提示用户可以实现的功能。同时我用颜色模拟出显示当前棋局耗用时间的文本框。

不论按钮还是单选按钮都要关联相应的消息，把相应功能的实现放在消息响应处理函数理。这些主要是实现Java库提供的消息响应接口里的方法。

5.chessPiece类

主要完成当前棋面的存储，存储棋面的数据结构为二维数组int[][]PositionFlag；然后定义获取、设置某点以及整个棋面的状态的方法。

(1)、SetPositionFlag(intx,inty,intflag)//设置（x,y）处的状态为flag

(2)、GetPositionFlag(intx,inty)//获取（x,y）处的状态

(3)、SetAllFlag(int[][]NewFlag)//设置当前整个棋面的状态为NewFlag

(4)、GetAllFlag()//获取当前整个棋面的状态

(5)、DrawChessPiece(Graphicsg)//绘制当前局面的棋子

由于本类比较重要，所以附上了代码，见源代码1。

6.chessBoard类

功能为绘制棋盘线。由于围棋的棋盘比较复杂，横线、竖线较多，且为了使棋盘美观，还要自定义窗口边框、棋盘边框、对弈双方边框等，对线宽、线型也有一定要求。有时要单像素线条，有时要多像素线条。对于多像素线条，我主要用了2种方法。

方法一：

在需要绘制多像素线条处首先绘制一条单像素线，然后根据线宽要求上下平移适当像素达到绘制多像素的目的。这样的方法适合绘制水平线或竖直线，绘制其他斜率的线条容易造成走样。在没有想到比较好的反走样编程思想后我选择了调用Java库中已经封装好的函数。

方法二：

为了克服方法一绘制非水平或竖直线时造成的走样，同时也为了更进一步学习Java语言，我猜想肯定会有类似OpenGL中设置线宽的画刷，于是上网网络找到了相应的画刷Stroke类。通过Java库实现绘制不同线宽的直线，达到了反走样效果。

7.chessOneStep类

这个类是为了配合chessList类实现悔棋以及在计算机下棋算法实现返回有效状态点而设计的。主要数据成员为

privateintx,y,weight；//其中x,y表示点坐标，weight表示将棋下到该点获得的估价值。

主要方法如下：

(1)、GetX()//获得当前对象的x坐标

(2)、GetY()//获得当前对象的y坐标

(3)、GetWeight()//获得当前对象的(x,y)处的估价值

8.chessList类

程序支持悔棋功能，为了实现悔棋，自定义了chessList类。这个类主要通过引入java.util.ArrayList和java.util.List实现集合的数据类型。然后自定义一些方法，如下：

（1）、AddStep(chessOneStepOneStep)//添加一步棋到List中

（2）、GetSize()//获得当前List的大小

（3）、ClearList()//清空List

（4）、RemoveLast()//删去List中的最后元素

由于每次删除当前List中的最后一个元素，实现后进先出，所以可以模拟栈的功能实现悔棋。

9.myCompare类

由于在计算机下棋的极大极小博弈树算法中需要对自定义对象chessOneStep按weight进行排序，所以引入了myCompare类，通过实现Comparator接口中的compare方法完成自定义对象排序。

10.chessPanel类

程序的自定义面板类，主要负责完成当前框架内容的显示。这是一个重要的与框架和图形显示密切相关的类。主要数据成员为

privatechessboardMyChessBoard;//当前显示棋盘

privatechesspieceMyChessPiece;//当前显示整个棋面的状态

主要方法如下：

（1）、chesspanel(chessboardMyChessBoard1,chesspieceMyChessPiece1)//构造函数，分别用MyChessBoard1和MyChessPiece1初始化MyChessBoard和MyChessPiece

（2）display(chessboardMyChessBoard1,chesspieceMyChessPiece1)//自定义显示回调函数，调用repaint()完成重新绘制游戏界面

（3）、paintComponent(Graphicsg)//核心方法，调用各种函数完成具体的绘制工作

11.chessPositon类

程序算法核心类，总的功能是控制人和计算机轮流下棋，以及调用chessPanel类中的display(chessboard,chesspiece)方法完成界面的实时刷新。关于chessPositon类，我在此将重点介绍。chessPosition类的主要数据成员如下：

;//当前显示棋盘

;//当前显示整个棋面的状态

;////当前显示面板

=newchesslist();//当前下棋集合，用于悔棋

finalprivatestaticintINF=(1<<30);//表示正无穷大的常量，用于极大极小博弈数搜索算法

publicstaticbooleanCanGo;//控制当前下棋一方

类的设计集中体现在成员方法的设计上。实现人机对战，只有语言是远远不够的，还要加入算法，用算法引导计算机下棋。下面介绍该类的方法成员：

（1）、chessposition(chesspanel,chessboard,chesspiece)//带有参数的构造函数

（2）、chessposition()

不带参数的构造函数

（3）、mouseClicked(MouseEventevent)

鼠标响应函数，负责人的下棋，根据鼠标点击的位置转换得到所在棋盘的相对位置。如果该位置不合法，即超出棋盘有效范围，点击无响应；如果该位置上已有棋，弹出消息框给出提示。这二者都要求重新给出下棋位置，即当前鼠标响应无效…直到点击到棋盘有效区域。

（4）、IsOver(int[][]Array,intx,inty)

判断当前int[][]Array对应的棋局是否结束，即一方五子连成一条直线。此处有两种思路，一种对当前棋面上的所有棋子都进行一次判断，具体为水平方向、竖直方向、与水平线成45度方向、与水平线成135度方向，只要有一个方向五子连成一条直线就说明有一方获胜，游戏结束；另一种思路为只在当前下棋的4个方向进行判断，我的程序采用的是第二种，所以IsOver方法除了int[][]Array参数外，还有x,y参数，（x,y）表示当前下棋的坐标点。

（5）display()

通过调用自定义面板类的显示回调函数用于重新显示游戏界面，达到每下一步棋及时更新游戏界面的目的。

（6）、GetValue(intflag,intnum)

估值函数，根据经验把棋局分成只有1颗棋相连，2颗棋相连且两端被封死，2颗棋相连且一端封死另一端活的，2颗棋相连且两端都是活的，同理3颗棋、4颗棋也各自可分3种情况。不同的情况对应不同的估价值。估价值的设定是决定计算机一方是否智能的一个关键因素。

（7）、GetPredictValue(intflag,intnum)

对未连成一片但通过再下一颗子就能连成一片的局面进行估值，这在双方下棋的有限步骤内是能产生重要影响的。如果每局棋仅考虑当前一步，是不可取的。

（8）、Evaluate(int[][]Array,intx,inty)

根据棋面具体情况以及预先设定的估值函数，对某个点对应的局面进行评估。由于每次双方只能下一颗棋，所以可以每次取当前局面的所有点中对应估值最大值点的估值作为整个局面的估值。

（9）、GetGreedNext()

计算机下棋方法1，对应难度等级为简单，采用贪心思想。每次下棋前在求得最有利点下棋，而是否最有利只是通过一步评估。算法伪码描述为：

Max取负无穷大

for(行i从0到15)

{

For(列j从0到15)

{

If((i，j)对应的位置无棋)

{

a.假设放上一颗由人控制的棋，求估价值；

b.假设放上一颗由计算机控制的棋，求估价值；

c.取二者中较大值作为(i,j）处的估价值tmp；

d.取tmp与Max较大值赋值给Max.

}

}

}

最终Max对应的点就是当前整个局面中最大的估值点。至于上述为什么要考虑双方都在该点下棋的情况呢？主要原因为下五子棋是个攻防兼备的过程，不仅要考虑自己对自己最有利，还要考虑对对手最不利，通俗来讲就是在自己赢的时候不能让对手先赢。

（10）、GetSearchNext(intLookLength)

derectSearch(int[][]Array,booleanwho,intdeepth)

计算机下棋方法2：直接搜索法,对应难度等级为中等。

每步棋最多有225个不同下法，若采用直接搜索法则对应的孩子节点有225个（在下棋过程中会逐渐减少），即每层有最多225个节点待扩展，这就决定了直接搜索进行不超过2次—主要原因有两点：

a.采用深度优先搜索需要递归，递归中状态过多可能会爆栈，我们知道递归是用栈机制来实现的；采用宽度优先搜索又需要存储为扩展的节点，这对内存容量要求很高。

b.不管深搜还是广搜，在时间复杂度为O(N^m)的情况下都是不能接受的。其中N为当前棋局的待扩展节点，最大225;m为搜索的深度。

综上所述，在采用直接搜索法时搜索深度不能太深，严格来说是应该控制在2层以内，在计算机运算速度在10^7次每秒的情况下，理论和实验都表明超过2层就会变得很慢且这种趋势成指数级增长。

直接搜索算法伪代码为

GetSearch(booleanflag，intdeep)

{

如果deep等于0，返回当前棋局估值；

for(行i从0到15)

{

For(列j从0到15)

{

If((i，j)对应的位置无棋)

{

如果轮到计算机下棋，置标志位为2

GetSearch(！flag，deep-1)；

如果轮到人下棋，置标志位为1；

GetSearch(！flag，deep-1)；

}

}

}

}

（11）、GetMinMaxsearchNext(intLookLength)

MinMaxsearch(int[][]Array,booleanwho,intdeepth)

计算机下棋算法3：极大极小博弈树法,对应难度等级为困难。五子棋是个博弈游戏，当前在寻找对自己最有利的下棋点时要尽可能保证对对手最不利，这种思想可以用极大极小博弈树

E. 如何用VC实现直线的反走样

网络反走样
在光栅图形显示器上绘制非水平且非垂直的直线或多边形边界时，或多或少会呈现锯齿状或台阶状外观。这是因为直线、多边形、色彩边界等是连续的，而光栅则是由离散的点组成，在光栅显示设备上表现直线、多边形等，必须在离散位置采样。由于采样不充分重建后造成的信息失真，就叫走样(aliasing)。而用于减少或消除这种效果的技术，就称为反走样(antialiasing)。

F. 图形学模拟题问题 越快越好

网上有题有答案.
《计算机图形学》模拟试题一

班级 学号 姓名 成绩
一、填空（1×20=20分）
1. 一个交互性的计算机图形系统应具有 、 、 、 、输入等五方面的功能。
2. 阴极射线管从结构上可以分为 、 和 。
3. 常用的图形绘制设备有 和 ，其中 支持矢量格式。
4. PHIGS和GKS将各种图形输入设备从逻辑上分为六种：定位设备、笔划设备、 、 、 和 。
5. 通常可以采用 和 处理线宽。
6. 齐次坐标表示就是用 维向量表示n维向量。
7. 平行投影根据 可以分为 投影和 投影。
二、名词解释（3×5=15分）
1. 图像：
2. 走样：
3. 段：
4. 4连通区域：
5. 主灭点：
三、简答与计算（6×5=30分）
1． 图形包括哪两个方面的要素？在计算机中如何表示它们？
2． 简述荫罩式彩色阴极射线管的结构和工作原理？
3． 在交互输入过程中，常用的管理设备的方式有哪些？试分别说明。
4． 举例说明奇偶规则和非零环绕树规则进行内外测试时有何不同？
5． 什么是观察坐标系？为什么要建立观察坐标系？
四、推导与计算题
1. 试用中点Bresenham算法原理推导斜率大于1的直线段的扫描转换算法。（要求写清原理、误差函数和递推公式，并进行优化）（15分）
2. 已知直线 ，求相对于该直线作对称变换的变换矩阵。（10分）
3．试作出图4-1中三维形体ABCDE的三视图（平移矢量均为1）。要求写清变换过程，并画出生成的三视图。（10分）
《计算机图形学》模拟试题二
一、填空（1×20=20分）
8. 一个交互式计算机图形处理系统包括图形软件和_____________，图形软件又分为_____________、_____________和 三部分。
9. 构成图形的要素包括 和 ，在计算机中通常用采用两种方法来表示图形，他们是 和 。
10. 荫罩式彩色显像管的结构包括 、 、 和 。
11. 目前常用的PC图形显示子系统主要由3个部件组成： 、 和一个ROM BIOS芯片。
12. 在交互输入过程中，图形系统中有_____________、 、 和其组合形式等几种输入（控制）模式。
13. 填充一个特定区域，其属性选择包括 、 和 。
二、名词解释（3×5=15分）
6. 像素点：
7. 实体：
8. 区域填充：
9. 窗口：
10. 透视投影：
三、简答与计算（6×5=30分）
6． 目前图形图像处理的相关学科有哪些？他们之间的关系如何。
7． 什么是光点？什么是象素点？什么是显示器的分辨率？
8． 试简要描述直线线宽的处理方式。
9． GKS有哪六种逻辑输入设备？通常在哪几个层次这些设备进行评价？
10． 什么是走样？什么是反走样？常用的反走样技术有哪些？
四、推导和计算题（8×4=32分，5题中任选4题）
1． 试用中点Bresenham算法原理推导第一象限中y=0到x=y半径为R的圆弧段的扫描转换算法。（要求写清原理、误差函数和递推公式，并进行优化）（15分）
....

是找这个么？

G. 简述几种常见反走样算法的基本原理

常用的反走样方法可以分为两类：其中一类基于提高分辨率即增加采样点；另一类反走样方法是把象素作为一个有限区域。
走样 光栅系统在理论上只能用光栅网格上的象素近似地描绘平滑的直线、多边形和诸如圆与椭圆那样的曲线图元的边界。它引起了锯齿或阶梯状，这种视觉人工痕迹是信号处理理论中被称为走样的错误采样的表现。 反走样 在光栅图形显示器上绘制。

H. 常用的反走样方法有哪些，各有什么特点

在光栅显示器上显示斜线的45º角时常会发生锯齿状，请考虑减少锯齿状效果的各种方法并说明采用这些方法的代价。
在光栅图形显示器上显示斜线时常会发生锯齿，这是由于直线或多边形边界在光栅图形显示器的对应图形都是由一系列相同亮度的离散象素构成的。这种用离散量表示连续亮引起的失真称为走样，而用于减少或消除这种效果的技术，称为反走样。
一般而言，减少锯齿有三种方法，下面以直线扫描转换为例，分别介绍三种方法：
（1） 提高分辨率
假设把显示器的分辨率提高一倍，虽然直线经过2倍的象素，锯齿也会增加一倍。但由于每个锯齿在X方向和Y方向都只有低分辨率的一半，所以效果看起来会好一些，这种改进方法是以4倍的存储器代价和4倍的扫描转换时间获得的。因此增加分辨率是不经济的方法，它只能减轻，不能消除锯齿。
（2） 简单的区域取样
在直线扫描算法假定象素是数学上的一个点，象素的颜色是由对应于象素中心的图形中一点的颜色决定的。但是，实际上象素不是一个点，而是一个有限区域。屏幕上所画的直线段不是数学意义上的无宽度的理想线段，而是一个宽度至少为一个象素单位的线条。因此，把屏幕上的直线看成是长方条形更为合理。在绘制直线条时，所有与该长方条相交的象素都采用适当的宽度给予显示。这要求显示器各象素可以用多灰度显示。例，设象素中心是在网格点上的不相交的正方形，象素的灰度与它落在直线条内的面积成正比。在多灰度黑白显示器上，若一个象素整个落在线条上，则将它置成前景色。若一个象素与线条部分相交，根据相交部分的大小来选择不同的灰度，相交部分大的象素前景色成分更多一些，相交部分小的象素前景色成分更少一些。这种方法将产生模糊的边界，以此来减轻锯齿效应。在实际应用中，常采用盒式滤波器
（3） 加权区域取样
加权区域取样方法采用更为优化的圆锥形滤波器。圆锥的底圆中心在当前象素中心，底圆半径为一个单位，锥高为1。当直线条经过该象素时，该象素的灰度值是在二者相交区域上对滤波器进行积分的积分值。用这种圆锥形滤波器有如下特点：一是接近理想直线的象素将被分配更多的灰度值。二是相邻两个象素的滤波器相交，所以直线条经过该相交区域时，将对这两个象素分配给适当的灰度值，这有利于缩小直线条上相邻象素的灰度差。

I. 求反走样直线算法

请看这个。。在MFC建立EXE即可void Mbline();
void AntDisline();double m_x0,m_y0,m_x1,m_y1;#include"InputDlg.h"
#define ROUND(a) int(a+0.5)void CTestView::Mbline()//走样函数直线
{
CClientDC dc(this);
COLORREF rgb=RGB(0,0,0);
x=m_x0;y=m_y0;k=(m_y1-m_y0)/(m_x1-m_x0);
d=0.5-k;
for(x=x0;x<=x1;x++)
{
if(d<0)
{
y++;
d+=1-k;
}
else
d-+k;
}
dc.TestOut(10,10,"走样直线")；
}
void CTestView::AntiDisline()//距离加权反走样直线
{
CClientDC dc(this);
double x,y,d,k;
k=(y1-y0)/(x1-x0);
d=0;x=x0+10;y=y0+10;
COLORREF rgb1=RGB(0,0,0),rgb2=RGB(0,0,0);
for(x=x0;x<=(x1+10);x++)
{
rgb1=RGB(d*255,d*255,d*255);
rgb2=RGB((1-d)*255,(1-d)*255,(1-d)*255);
dc.SetPixel(ROUND(X),ROUND(Y+1),rgb2);
d+=k;
if(d>1.0)
{
y++;
d--;
}
}
dc.TestOut(10,100,"反走样直线")；
}
void CTestView::OnMENUAntiliasing()
{
InputDlg dlg;
if(dlg.DoModal()==IDOK)

{
x0=dig.m_x0;
y0=dig.m_y0;
x1=dig.m_x1;
y1=dig.m_y1;
}
AfxGetMainWnd()->SetWindowTest("反走样：直线距离权反走样算法")；
RedrawWindow();
Mbline();
AntiDisline();
}

J. 计算机图形学问题

1、直线的生成和2种算法：DDA算法：代码如下
void
dda(Graphics
g,int
x1,int
x2,int
y1,int
y2)
{int
k;
float
x,y,dx,dy;
k=Math.abs(x2-x1);
if(Math.abs(y2-y1)>k)
k=Math.abs(y2-y1);
dx=(float)(x2-x1)/k;
dy=(float)(y2-y1)/k;
x=(float)x1;
y=(float)y1;
for(int
i=0;i<k;i++)
drawLine((int)x+.5f,((int)y+.5f,((int)x+.5f.((int)y+.5f);
x=x+dx;
y=y+dy;
}
}
Breseham算法；
2、填充的定义和2种算法分别是
扫描线种子填充算法和递归算法
3、图像学的定义与运用
定义是研究如何在计算机环境下生成，处理和现实图形的一门学科。具体应用很广泛：像有些公司在制造汽车，飞机等时，会先画出制图，一般都会在计算机上绘制出来；等等吧