计算机图形学第5章

《计算机图形学第5章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、4P5,P2X4,Y4P4,P5P2,P4X5,Y5P5,P1P4,P1可见，为了唯一地表达一个图形，描述该图形的数据必须带有两种信息：（１）几何信息：描述图形的几何位置关系；（２）拓扑信息：说明图形的构成规则。如何把构成图形的几何、拓扑两种信息组合在数据描述中，这就形成了不同的数据结构形式。但不管形式如何，都必须满足一些基本的条件：能够描述图形的几何关系和拓扑关系；描述是完整、唯一的；便于对数据进行各种处理；数据的冗余量要小。对于一般的图形描述，常用的数据结构有两种形式：（１）线性表结构。特点：算法简单，存储量少，效率低。（２）层次（树形）结构。特点：算法较复杂，

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

4、时间不随元素的位置而变。２.线性表的常用运算：（１）删除运算（删除ti，并保持线性连续）t(j-1):=t(j)运算示意如下：t(1),t(2),…，t(i),t(i+1),…t(n)步骤：ifi1orinthenreturnelse[forj=i+1tondot(j-1):=t(j);n:=n-1;return]（2）插入运算（在ti之前插入Ｘ）t(j＋1):=t(j)运算示意如下：t(i):=X;t(1),t(2),…，t(i-1),t(i),t(i+1),…t(n)Ｘ步骤：ifinthen[n:=n+1;t(n)=X;return]else[ifi1t

5、heni:=1;forj=ndowntoidot(j+1):=t(j);t(i):=X;n:=n+1;return]（３）排序运算按规定的次序重新安排给定的一组对象。（排序是查找的基础）简单插入排序：把一个记录，按其关键字的值，插到一组已经排好序的记录中去。（适合于表的长度较短）简单插入排序的算法：fori=2tondo[x:=t(i);j:=i-1;while(xt(j)and(j1))do[t(j+1):=t(j);j:=j-1]t(j+1):=x]算法示意图如下：t(1),t(2),…t(i-1)，t(i),…t(n)折半插入排序改变关键字比较的顺序：在简

6、单插入排序中，当前记录的关键字是从后往前逐个比较，以确定位置；而在折半插入排序中，当前记录的关键字是和前面一组记录的中间记录进行比较，以确定位置。算法示意图如下：t(1),...t(m),…t(i-1)，t(i),…lowmhigh折半插入排序算法：fori=2tondo[x:=t(i);low:=1;high:=i-1;whilelowhighdo[m:=(low+high)/2;ifxt(m)thenhigh:=m-1elselow:=m+1]forj=i-1downtolowdot(j+1):=t(j);t(low):=x]冒泡排序通过多次重复比较一组记录

7、中两个相邻记录的关键字，并调整它们的位置，从而完成排序。３.线性表的应用及不足：在图形程序中，可用线性表对简单的图形（包括二维和三维）进行建模：顶点表（各顶点坐标）边表（各顶点间的连边规则）但由于图形间的运算，使得两表不断改变，致使表中元素搬家频繁。因此，线性表适用作静态表。见图例。图形间的运算，使得图形的几何关系和拓扑关系经常发生变化。三、链表结构链表是由结点组成的数据表，每个结点由数据域和指针域构成。表的连续性由各结点的链指针来维持，而不必靠顺序存储来维持，使得其物理结构相当灵活。下面是一个单向链表的示意图。（１）链表的删除运算：删除一个结点，仅须修改该结点