计算机图形学第5章.ppt

1、第5章 图形数据结构,一、数据结构概述 图形对于人的视觉来说是直观的、极 易接受的。但计算机如何依靠视觉来 接受一个图形，这就要研究图形的数 据描述及在机内的表达和存储模式。 图形数据结构要研究解决的问题就包 括了有关的这些内容。,例如我们看下面这个由五条线段组成 的不同图形： 同样是五个点、用五条边，但由于 连接方法不同，所以构成不同的图形。,a. 五个点b. 五边形c. 五角星,两个不同的图形，其组成的顶点元素 相同，即五个顶点坐标相同。但由于 连边规则不同，致使构成不同的图形。 见下面三个表： 顶点表五边形五角星 X1 , Y1 P1 , P2 P1 , P3 X2 , Y2 P2 ,

2、P3 P3 , P5 X3 , Y3 P3 , P4 P5 , P2 X4 , Y4 P4 , P5 P2 , P4 X5 , Y5 P5 , P1 P4 , P1,可见，为了唯一地表达一个图形，描 述该图形的数据必须带有两种信息： （）几何信息：描述图形的几何位 置关系； （）拓扑信息：说明图形的构成规 则。,如何把构成图形的几何、拓扑两种信 息组合在数据描述中，这就形成了不 同的数据结构形式。但不管形式如何， 都必须满足一些基本的条件： 能够描述图形的几何关系和拓扑 关系； 描述是完整、唯一的； 便于对数据进行各种处理； 数据的冗余量要小。,对于一般的图形描述，常用的数据结 构有两种形式：

3、 （）线性表结构。 特点：算法简单，存储量少， 效率低。 （）层次（树形）结构。 特点：算法较复杂，存储量大， 效率较高。,二、线性表结构 .线性表的定义 线性表是 n（n=0）个元素的有限序 列，当n0时，表中的每个元素除了 第一个和最后一个外，都有一个且只 有一个直接的前趋和后继。 （线性连续）,线性表的逻辑结构： （t1,t2,t3,tn） n：表中包含元素的个数，即表的长 度。当n=0时，称为空表。 线性表的物理结构： 在存储器中连续顺序分配存储，这是 维持线性连续的手段。存储地址和元 素的下标一一对应。,元素的物理寻址公式： loc(ti)=ad1+(i-1)len ti: 表中第

4、i个元素。 ad1:存储块起始地址。 len:单个元素的存储长度。 特点：地址计算简单，存取方便，存 取所需的时间不随元素的位置 而变。,.线性表的常用运算： （）删除运算 （删除ti，并保持线性连续） t(j-1):=t(j)运算示意如下： t(1),t(2),，t(i),t(i+1),t(n),步骤：if i1 or in then return else for j=i+1 to n do t(j-1):=t(j); n:=n-1; return ,（2）插入运算（在ti之前插入） t(j1):=t(j)运算示意如下： t(i):=X; t(1),t(2),，t(i-1), t(i),t

5、(i+1),t(n),步骤：if inthen n:=n+1; t(n)=X; return else if i1 then i:=1; for j=n downto i do t(j+1):=t(j); t(i):=X; n:=n+1; return ,（）排序运算 按规定的次序重新安排给定的一组对 象。（排序是查找的基础） 简单插入排序： 把一个记录，按其关键字的值，插到 一组已经排好序的记录中去。 （适合于表的长度较短）,简单插入排序的算法： for i = 2 to n do x := t ( i ); j := i-1; while ( xt ( j ) and ( j1) do t

6、 ( j+1) := t ( j ); j :=j-1 t ( j+1) := x,算法示意图如下： t(1),t(2), t(i-1)，t(i),t(n),折半插入排序 改变关键字比较的顺序：在简单插入 排序中，当前记录的关键字是从后往 前逐个比较，以确定位置；而在折半 插入排序中，当前记录的关键字是和 前面一组记录的中间记录进行比较， 以确定位置。,算法示意图如下： t(1),.t(m), t(i-1)，t(i), low m high,折半插入排序算法： for i=2 to n do x:=t(i); low:=1;high:=i-1; while lowhigh do m:=(low

7、+high)/2; if xt(m) then high:=m-1 else low:=m+1 for j=i-1 downto low do t(j+1):=t(j); t(low):=x,冒泡排序,通过多次重复比较一组记录中两个相邻记录的关键字，并调整它们的位置，从而完成排序。,.线性表的应用及不足： 在图形程序中，可用线性表对简单的 图形（包括二维和三维）进行建模： 顶点表（各顶点坐标） 边表（各顶点间的连边规则） 但由于图形间的运算，使得两表不断 改变，致使表中元素搬家频繁。因此， 线性表适用作静态表。见图例。,图形间的运算，使得 图形的几何关系 和拓扑关系经常 发生变化。,三、链表结

8、构 链表是由结点组成的数据表，每个结 点由数据域和指针域构成。表的连续 性由各结点的链指针来维持，而不必 靠顺序存储来维持，使得其物理结构 相当灵活。 下面是一个单向链表的示意图。,（）链表的删除运算： 删除一个结点，仅须修改该结点之前 一结点的链指针值即可。 见示意图。,删除结点 i,算法执行的结果： 做到 j=i-1 步，即可得到第 i个结点的 地址（第i-1 个结点的链指针值）。 让 (i-1).link (i).link，这样第（i-1） 个结点的链指针就直接指到第（i+1） 个结点上，致使第i个结点被删除。,链表的删除运算算法： if i=1 then head:=head.link

9、 else b:=head.link; for j=1 to i-1 do f:=b;b:=f.link f.link:=b.link put back a node; sum:=sum-1; return;,（）链表的插入运算： 算法执行的结果： 做到 j 步，即记下了第 j个结点的地址 （即 f 的值）;并取得了下一个（j+1) 结点的地址 b。于是 new.link:=b; f.link:=new； 完成了在第 i个结点之前插入一个结点 的工作。,take a new node; new.data := x ; if i1 then new.link:=head; head:=new e

10、lse if isum then i:=sum+1; b:=head.link; for j=1 to i-1 do f:=b ; b:=f.link new.link:=b; f.link:=new sum:=sum+1;return;,多重链表,单向链表进行查找时，总是往后进行，这样查找前趋接点就不直观，为了提高查找的灵活性，可以给接点增加一个链域，用来存放指向该接点前趋接点的指针。,链表结构是树形结构的基础。因为在 树形结构中，构成树的基本单位是多 重链结点，即一个结点中包含有多个 链指针域，可以用来分别指向多个结 点，以形成分支。一棵树中的所有结 点，包括叶子结点，都是由这种链结 点组

11、成的。,二叉树,二叉树是接点的有限集合，这个集合或者是空的，或者是由一个称为根的接点以及该根的两个互不相交的左子树和右子树构成。,树形结构,二叉树的遍历,中序遍历：若二叉树为空，则退出；否则，先遍历左子树，再访问根接点，最后遍历右子树。 后序遍历：若二叉树为空，则退出；否则，先遍历左子树，再遍历右子树，最后访问根接点。 前序遍历：若二叉树为空，则退出；否则，先访问根接点，再遍历左子树，最后遍历右子树。,中序遍历：C,B,E,D,A,G,H,I,F,J 后序遍历：C,E,D,B,I,H,G,J,F,A 前序遍历：A,B,C,D,E,F,G,H,I,J,图形的层次结构,CSG树,四、栈的结构和应用 栈是一种特殊形式的线性表。该表只 有一端是开口的，而另一端则是封闭 的。因此，对表中元素的存取只能在 开口的一端进行，这就形成了栈的存 取特点后进先出。,栈的操作过程： (1)进栈 假