第三章 空间数据结构教程文件.ppt

第三章 空间数据结构与编码; 空间数据结构与数据编码;栅格数据结构：应用与图像处理系统和GIS中。 矢量数据结构：主导了CAD系统和有着强大制图功能的GIS。;一、基于规则格网空间数据模型的数据 结构 (栅格数据结构);（一）概念; 点用一个栅格单元表示； 线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上； 面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。 ;（二）基本特征;（三）栅格数据的组织;（四）栅格结构的建立;（四）栅格结构的建立;（四）栅格结构的建立;每个栅格元素只能取一个值，实际上一个栅格可能对应于实体中几种不同属性值，存在栅格数据取值问题;1、中心点法 用处于栅格中心处的地物类型或现象特性决定栅格代码。 中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等 。;2、面积占优法 以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码 。 用于分类较细，地物类别斑块较小的情况。 ;3、长度占优法 将网格中心画一横线，用横线所占最长部分属性值作为栅格属性;4、重要性法 突出某些主要属性，只要在栅格中出现就把该属性作为栅格属性;5、百分比法 根据矩形区域内各地理要素所占面积的百分比数确定单元的取值。;（五）栅格数据编码方式;（五）栅格数据结构类型;2;优点： 1易于实现用循环语句编程，实现快速运算 2易于实现空间属性的分解与分类，易于实现空间分析中叠加等操作;（2）费尔曼链码 （边界编码）;（2）费尔曼链码 （边界编码）;2;特征码; 优缺点： 数据压缩率强，便于计算长度，面积，转折方向的凸凹度，易于储存。 但难于实现叠置运算，不便于合并插入操作。对局部改动涉及到整体结构。;（3）游程（行程）编码 ;（3）游程（行程）编码 ;编码方式：(gk，lk) gk—栅格属性值 lk —游程终止列号或长度 K=1,2,3,4…..m(mn);(0,1) (4,3) (7,8) (4,5) (7,8) (4,4) (8,6) (7,8) (0,2) (4,3) (8,6) (7,8) (0,2) (8,6) (7,7)(8,8) (0,3) (8,8) (0,4) (8,8) (0,5) (8,8) ;（0,1) (4,2) (7,5) (4,5) (7,3) (4,4) (8,2) (7,2) (0,2) (4,1) (8,3) (7,2) (0,2) (8,4) (7,1) (8,1) (0,3) (8,5) (0,4) (8,4) (0,5) (8,3) ; 特点：属性的变化愈少，游程愈长，即压缩比的大小与图的复杂程度成反比。 优点：数据压缩率高，易于实现叠加，检索和合并运算。 缺点：适合类型区面积较大的专题图、遥感影像分类集中的分类图，不适合类型连续变化或类型区分散的分类图。;（4）块状编码;0 2 2 5 5 5 5 5;特点： 1、面状地物所能包含的正方形越大，多边形边界越简单，块码编码效率超高； 2、图形比较碎，多边形边界复杂的图形，数据压缩率低； 3、利于计算面积、合并插入等操作。;（5）四叉树编码（Quadtree Code）;（5）四叉树编码（Quadtree Code）;0;1）常规四叉树及编码;对一幅2N ×2N的栅格阵列，最大深度为N，可能有的层次为0，1，2，…，N，最大层数为N+1.那么，每层的栅格宽度为： 2（最大深度-当前层次） 反映了所在叶结点表示的正方形集合的大小。;缺点： 所占空间比较大，不仅要记录每个结点，还要记录一个前趋结点和四个后继点，以及反映结点之间联系，对栅格数据进行运算时，还要作遍历树结点的运算，增加操作复杂性。;2)线性四叉树及编码;2)线性四叉树及编码;(19) 0;2）线性四叉树及编码;8 9 8;（2）基于四进制的线性四叉树编码;333;;四进制线性四叉树编码的特点： 优点是便于实现行列值及其编码之间的转换； 缺点是存储开销大，且一般软件都不支持四进制。;（3）基于十进制的线性四叉树编码;表a经自下而上归并得表b。依次检查表a中四个相邻叶结点的属性代码是否相同。若相同则归并成一个父结点，记下地址及代码。否则不予归并。然后再归并更高一层父结点，如此循环，直到不能归并为止。;63;0;特点：比四进制节省储存空间，且前后两个MD码之间差代表了叶结点的大小，还可进一步利用游程编码对数据进行压缩。 优点：具有可变分辨率，能精确表示图形的细节部分，编码效率高；具有区域性质，适合于图形图像的分析运算；便于岛的分析。;（三）四叉树优缺点;（三）四叉树优缺