4 图形的表示与数据结构

1.1 算法考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。

算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

1算法的基本特征(1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。

(2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。

(3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。

(4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。

2算法的基本要素(1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。

计算机可以执行的基本操作是以指令的形式描述的。

一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。

计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类：①算术运算：主要包括加、减、乘、除等运算；②逻辑运算：主要包括“与”、“或”、“非”等运算；③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算；④数据传输：主要包括赋值、输入、输出等操作。

(2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。

算法中各操作之间的执行顺序称为算法的控制结构。

算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。

基本概念——平面多面体与欧拉公式
欧拉公式证明简单多面体的顶点数V、边数E和面
数F满足如下关系：V-E+F=2。
非简单多面体需对欧拉公式加以扩展。令 H表示
多面体表面上孔的个数， G表示贯穿多面体的孔
的个数， C表示独立的、不相连接的多面体数，
则扩展后的欧拉公式为：V-E+F-H=2（C-G）。
9
基本概念——实体
图4.2 带有悬挂边的立方体
10
基本概念－实体
点的领域：如果P是点集S的一个元素，那么点P的以R
（R>0）为半径的领域指的是围绕点 P的半径为 R的小
球（二维情况下为小圆）。
开集的闭包：是指该开集与其所有边界点的集合并集，
本身是一个闭集。 正则集：由内部点构成的点集的闭包就是正则集，三维 空间的正则集就是正则形体。
的体素，然后，以体素的集合来表示图形对
象。
二维情况，常用二维数组存放。
三维情况下，常用三维数组 p[i][j][k] 来存
放。
37
八叉树
八叉树（ octrees）又称为分层树结构，它对 空间进行自适应划分，采用具有层次结构的八 叉树来表示实体。
38
八叉树——四叉树
象限1 象限2 1 2 3 4 B B B B E B F B E B B B 象限4 (a) 象限3 E E F E F F F F (b) E E F E F F F E E F E E ...... B F F B
图4.12 三角形带与四边形网格
30
扫描表示（sweep representation）
扫描表示法（sweep representation）可以利用 简单的运动规则生成有效实体。 包含两个要素 一是作扫描运动的基本图形（截面）； 二是扫描运动的方式。

顺序存储方法是把逻辑上相邻的结点存储在物理
位置______的存储单元中。 答：相邻
假设线性表的每个元素需占用K个存储单元，并以所占 的第一个单元的存储地址作为数据元素的存储位置。则 线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i 个数据元素的存储位置LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+K LOC(ai)=LOC(a1)+(i-1)*K ① 其中，LOC(a1)是线性表的第一个数据元素a1的存储位 置，通常称做线性表的起始位置或基地址。 因为在顺序存储结构中，每个数据元素地址可以通过公 式①计算得到，所以线性表的顺序存储结构是随机存取 的存储结构。 在线性表的顺序存储结构下，可以对线性表做以下运算： 插入、删除、查找、排序、分解、合并、复制、逆转
九.顺序表的删除运算
线性表的删除运算是指在表的第I个位置上，删 除一个新结点x，使长度为n的线性表 （a1,a2 …ai…an）变成长度为n-1的线性表 (a1,a2…ai-1,ai+1…an). 当I=n,时间复杂度o(1),当I=1,时间复杂度o(n) , 平均时间复杂度为o(n)
顺序表的插入运算过程
六.线性表的定义
线性表是n 个元素构成的有限序列（A1，A2， A3……）。表中的每一个数据元素，除了第一个 以外，有且只有一个前件。除了最后一个以外有 且只有一个后件。即线性表是一个空表，或可以 表示为（a1,a2,……an）, 其中ai(I=1,2,……n) 是属于数据对象的元素，通常也称其为线性表中 的一个结点。 非空线性表有如下一些特征： （1）有且只有一个根结点a1,它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有 且只有一个前件，也有且只有一个后件。线性表 中结点的个数n称为线性表的长度。当n=0时称为 空表。

电子信息工程专业《计算机图形学》教学设计卢迪王鹏张开玉哈尔滨理工大学电气与电子工程学院20XX年9月1 课程的基本描述课程名称：计算机图形学Computer Graphics课程性质：学科基础必修课适用专业：电子信息工程教材选用：陈传波，陆枫. 计算机图形学基础.北京：电子工业出版社，2002总学时：60 理论学时：48实验学时：12 课程设计：无学分： 3.5 开课学期：第六学期前导课程：高等数学、线性代数、C语言程序设计后续课程：数字图像处理2 教学定位2.1 能力培养目标本课程主要培养学生以下三个方面的能力：1. 认知和理解能力理解计算机图形学的基本概念、图形的表示与数据结构、曲线曲面的基本概念。

2. 逻辑思维能力理解基本图形的生成算法，并能对现有的算法进行改进，理解图形的变换和裁减算法。

3. 程序设计能力能够根据图形生成算法、裁剪算法设计相应的实现程序。

2.2 课程的主要特点计算机图形学是研究怎样利用计算机来显示、生成和处理图形的原理、方法和技术的一门学科。

是一门复杂的综合性的新兴学科，内容丰富，涵盖的知识面较广。

既有具体的图形软硬件，又有抽象的理论和算法。

为学生以后从事图形图像处理工作打下坚实的基础。

2.3 教学定位计算机图形学是一门应用广泛的新兴学科，主要介绍图形标准、图形硬件、图形的表示、基本图形的生成算法，以及图形的变换和观察等。

通过本课程的学习，学生可以了解图形系统的框架及其涉及的软件、硬件技术；了解图形学的基本问题，掌握图形学的基本概念、方法与算法；对于图形相关的应用及当前的研究热点有一个初步认识；具有一定实践体会和相关的编程能力。

3 知识点与学时分配3.1 计算机图形学及其相关概念计算机图形学及其相关概念、计算机图形系统（学时：0.5学时）计算机图形学、图形的要素、图形的表示方法（理解、核心）计算机图形学与相关学科间的关系（了解、推荐）计算机图形系统的功能（理解、核心）计算机图形系统的结构（了解、推荐）计算机图形学的发展、应用、研究动态（学时：1.5学时）计算机图形学的发展、计算机图形学的应用、计算机图形学的研究动态（了解、推荐）共2学时3.2 图形设备图形输入设备（学时：1.5学时）键盘、鼠标、光笔、触摸屏、图形扫描仪（理解、核心）操纵杆、跟踪球、数据手套、数字化仪、声频输入系统（了解、可选）图形显示设备（学时：2学时）阴极射线管、CRT图形显示器（理解、核心）平板显示器、三维观察设备（了解、可选）图形显示子系统（学时：2学时）显示子系统的结构（理解、核心）分辨率、像素与帧缓存、颜色查找表、显示长宽比（理解、核心）PC图形显示卡（了解、可选）图形绘制设备（学时：0.5学时）打印机、绘图仪（理解、推荐）共6学时3.3 图形的表示与数据结构基本图形元素与段（理解、推荐）几何信息与拓扑信息、坐标系、几何元素（理解、核心）实体、正则集合运算（了解、可选）共2学时3.4 图形的生成、变换和观察基本图形生成算法（学时：12学时）直线的扫描转换（数值微分法、中点Bresenham算法、改进的Bresenham算法）（运用、核心）圆的扫描转换（简单方程产生圆弧、中点Bresenham画圆）（运用、核心）椭圆的扫描转换（椭圆的中点Bresenham画圆）（运用、核心）多边形的扫描转换与区域填充（X扫描线算法、改进的有效边表算法、边缘填充算法、边界填充算法、泛填充算法）（运用、核心）字符处理、属性处理（了解、推荐）反走样（过取样、简单的区域取样、加权区域取样）（理解、核心）二维变换及二维观察（学时：10学时）基本概念（齐次坐标、几何变换、二维变换矩阵）（理解、核心）基本几何变换（平移变换、比例变换、旋转变换、对称变换、错切变换、二维图形几何变换的计算）（运用、核心）二维观察（基本概念、用户坐标系到观察坐标系的变换、窗口到视区的变换）（运用、核心）裁减（点的裁减、直线段的裁减、多边形的裁减、其他裁减）（运用、核心）三维变换及三维观察（学时：4学时）基本概念（三维齐次坐标变换矩阵、几何变换、平面几何投影、观察投影）（理解、核心）三维几何变换（三维基本几何变换、三维复合变换）（理解、核心）共26学时3.5 曲线和曲面基本概念（学时：2学时）曲线曲面数学描述的发展（了解、推荐）曲线曲面的表示、插值和逼近样条、样条描述（理解、核心）三次样条（学时：2学时）自然三次样条、三次Hermite样条（理解、核心）Bezier曲线曲面（学时：2学时）Bezier曲线定义和性质（理解、核心）Bezier曲线的生成（了解、可选）B样条曲线曲面（学时：2学时）定义、性质（理解、核心）B样条曲面（了解、可选）共8学时3.6 其它学时习题课(学时：4学时)实验(学时：12学时)3.7 课程覆盖的知识领域和知识单元汇总4 讲授提示及方法4.1计算机图形学及其相关概念重点：计算机图形学的定义、图形的要素、图形的表示方法、计算机图形系统的功能。