还剩2页未读,继续阅读
文本内容:
三维数据结构及其分类姓名:班级:学号:日期:三维数据结构及其分类
一、引言随着GIS理论的日趋成熟及其应用的不断拓展,其很多商业化的GIS软件的功能也渐渐完善但是绝大多数的商品化GIS软件包还只是在二维平面基础上对现实世界的实体及实体之间的关系的模拟和处理,而我们生活在三维的世界里,所涉及到的有关气象、水文、采矿、灾难、污染等方面的自然现象都是三维的,明显当我们仅仅用二维的方法和思路解释和处理三维问题时,就不能够精确地或正确地反映、存储、分析、处理和显示地理空间信息因此,为更逼真精确地描述现实三维世界,研讨和讨论三维数据结构显得尤为重要
二、三维数据结构数据结构是即数据的规律结构形式,我们所熟识的是二维数据结构,从类别上分,二维数据结构包括矢量数据结构、栅格数据结构、矢量-栅格一体化数据结构等,这主要是依据其数据模型进行分类的,即栅格数据模型、矢量数据模型、面对对象数据模型等,这与我们通常先建立数据模型,再依据数据模型选用合适的数据结构对数据进行组织的思路是全都的通常我们所说的三维景观可视化和已经具有的
2.5维表面建模都还不是真正意义上的三维,比如采用DEM数据建立的三维景观模型可视化,或者采用多属性的实体的某一属性作为第三维对平面图形进行三维显示等如采用v=fx,y表达一个二维系统,x,y是二维平面坐标,v是对应点的属性值,当v表示高程时,就可以表示数字高程模型但这里v受x,y变化的影响;而真正意义上的三维数据模型中,三维变量之间应是相互独立的也就是说,对于一个真正的三维数据模型,可以用V=fx,y,z来描述,其中z是自变量,不受x,y变化的影响,即x,y,z是在三维空间连续变化的总的来说,即是与二维相比,三维多出了一维,但仍旧可以将二维的观点引入对三维的讨论之中三维空间数据模型是人们对客观世界的理解和抽象,是建立三维空间数据库的理论基础三维空间数据结构是三维空间数据模型的详细实现,是客观对象在计算机中的底层表达,是对客观对象进行可视表现的基础引入二维空间数据模型的部分理念后,且在三维空间里进一步作适当合理的扩展,地理实体可以分为点、线、面和体四种基本元素,由这四种元素构成简单的三位目标这样,将地理实体的三维空间分成细小的单元,称之为体元素或体元,并将其作为三维空间讨论的原子项,并用二值化的思想推断体元与实体之间的关系,即体元包含在实体内,则赋值为1,否则赋值为.体元可以是正立方体、正方体、四周体或其它非规章外形等在对三维数据模型作了较为成熟的熟识之后,三维数据结构的建立便于有了肯定的依据为了实现将三维的空间实体模型在计算机之中存储、处理、检索、查询、分析和显示,必需采用适于计算机表达、存储和管理的三维数据结构对现实建立的三维数据模型进行表达同样,考虑二维数据结构,并将其在三维空间进行拓展,可以得到对应的三维数据结构,即八叉树三维数据结构采用八叉树来表示三维形体,既可以看成是四叉树方法在三维空间的推广,也可以是用三维体素列阵表示形体方法的一种改进其规律结构可以定义如下假设要表示的形体T可以放在一个充分大的实体C内,C的边长为2L形体TC,它的八叉树可以用以下递归的方法来定义八叉树的每个节点与C的一个子立方体对应,树根与C本身相对应,假如T=C,那么T的八叉树仅有树根,假如T不等于C,则C等分为八个子立方体,每个子立方体与树根的一个子节点相对应只要某个子立方体不是完全空白或完全为T所占据,就要被八等分,从而对应的节点也就有了八个子节点这样递归推断、分割始终要进行到节点所对应的立方体或是完全空白,或者是完全为T占据,或是其大小已是预先定义的体素大小,并且对它与T之交作肯定的“舍入”,使体素或认为是空白的,或认为是T占据的如此所生成的八叉树上的节点可以分为三类一是灰节点,对应的立方体部分地为T所占据;二是白节点,对应的立方体中无T的内容;三是黑节点,对应的立方体全为T所占据后两类又称为叶节点与四叉树结构相类似的八叉树结构可以沿用四叉树的有关方法依据存储方式的不同,八叉树可以分为常规的、线形的、一对八的八叉树等等1)规章的八叉树八叉树的存储结构是用一个有九个字段的纪录来表示树中的每个结点,其中一个字段用来秒苏该结点的特性,其余的八段用来作为存放指向其八个子结点的指针但是规章八叉树的缺陷较多,最大的问题就是指针占用了很大的空间因此虽然其易于理解把握,但存储代价太大2)线形八叉树线形八叉树注意考虑的是如何提高空间采用率,用某一预先确定的次序遍历八叉树,将八叉树转换成一贯线形表,表的每个元素与一个结点相对应线形八叉树不仅节约存储空间,对某些运算也比较便利,但是不够敏捷3)一对八式的八叉树在一对八式的八叉树中,一个非叶结点有八个子结点,假如一个纪录与一个结点对应,那么在这个纪录中描述的是这个结点的八个子结点的特征值,而指针给出的则是该八个子结点所对应纪录的存放处,而且还隐含地假设了这些子结点纪录存放的次序也就是说,即使某个纪录是不必要的,那么相应的存储位置也必需空闲在那里,以保证不会错误地存取到其它同层结点的纪录很明显,当它不是完全八叉树的时候,存储空间会有肯定的铺张为了克服这种缺陷,一是增加计算量,即在存取相应结点纪录之前,首先检查它的父结点纪录,看一下之前有几个叶结点,从而可以知道应当如何存取所需结点纪录这种方法可以减小存储需求,但会增加计算量;另一个是在纪录中增加肯定的信息,使计算工作适当削减或者更便利例如在原纪录中增加三个字节,一分为八,每个字节点对应三位,代表它的子结点在指针指向区域中的偏移因此,要找到它的子结点纪录位置,只要固定地把指针指向的位置加上这个偏移量乘上纪录所占的字节数,就是所要的位置,因而一个结点可以描述为偏移指针SWE SWTNWB NWTSET SEBNET NEB用这种方式所得到的八叉树和以前相同,只是每个纪录前多了三个字节
三、分类与二维数据结构类比,可将三维数据结构分为三维矢量数据结构、三维栅格数据结构、矢量栅格一体化三维数据结构、面对对象三维数据结构、镶嵌数据结构等基于镶嵌数据模型的三维数据结构可以采用有四周体格网法、单纯形剖分法、空间枚举法、单元分解法等表达;基于矢量的数据模型的三维数据结构可以采用线框表示法、实体模型法、表面剖分法等表达;基于分析型的数据模型的三维数据结构可以采用非匀称有理B样条函数等进行表达;此外还有混合型数据结构,其可用构造几何体法、面对对象思想以及与树结构相结合进行表达其中三维数据结构的最重要的一个分类依据就是实际应用,通过对现实世界表达的需要分析以寻求采用一种合适的三维数据结构来表达三维空间实体及实体之间的关系但其从二维空间数据结构进行拓展来定义三维数据结构以及结合三维的特点在适当三维模型构建的基础之上进行三维数据结构的定义对采用三维数据结构来讨论现实世界的三维空间实体以及其关系供应了科学的方法
四、结论三维数据模型的构建和三维数据结构的组织对于三维空间数据的收集、存储、管理、分析、表达和显示是不行或缺的三维数据模型具有较为直观的表达效果,而依据其进行三维数据组织,即设计适合计算机存储、管理、分析和表达的三维数据结构是一种物理实现,其对现实世界的表达的逼真程度是评价其质量的重要指标因此对三维数据的结构的表达方式的探究讨论,是对现实世界水文、经济、灾难等三维空间实体进行优化表达以及应用的重要前提,并为其奠定了坚实的理论基础。