第二空间数据结构演示文稿.pptVIP

2、矢栅一体化概念 将矢量面对目标的方法和栅格元子充填的方法结合起来，具体采用填满线状目标路径和填充面状目标空间的方法作为一体化数据结构的基础。 线状地物：除记录原始取样点外，还记录路径所通过的栅格。 面状地物：除记录它的多边形周边以外，还包括中间的面域栅格。 一方面，它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系； 另一方面，它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。 3 3 4 3 3 4 4 2 3 3 4 4 4 2 3 3 4 4 2 3 4 4 2 2 2 1 2 从原理上说，这是一种以矢量的方式来组织栅格数据的数据结构。 矢栅一体化数据结构 当前第63页\共有88页\编于星期五\9点 3、三个约定和细分格网法 为便于组织数据，首先作如下约定： a. 地面上的点状地物是地球表面上的点，它仅有空间位置，没有形状和面积，在计算机内部仅有一个位置数据。 为提高栅格表示精度，采用细分格网法： 将一对X,Y坐标用两个Morton码代替： 前一M1表示该点所在基本格网的地址码，后者M2 表示该点对应的细分格网的Morton码，既顾全整体定位，又保证精度。 b. 地面上的线状地物是地球表面的空间曲线，它有形状但没有面积，它在平面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组元子填满整个路径。 c. 地面上的面状地物是地球表面的空间曲面，并具有形状和面积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组成。 x,y M1 M2 矢栅一体化数据结构 当前第64页\共有88页\编于星期五\9点 4、一体化数据结构设计 线性四叉树(Morton)是基本数据格式，三个约定设计点、线、面数据结构的基本依据，细分格网法保证足够精度。 点标识号 M1 M2 高程Z …… …… …… …… 10025 43 4084 432 10026 105 7725 463 …… …… …… …… 只要将点的坐标转化为地址码M1 和M2 ,结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。 1) 点状地物和结点的数据结构 矢栅一体化数据结构 当前第65页\共有88页\编于星期五\9点 2) 线状地物的数据结构 线状地物有形状但没有面积，没有面积意味着只要用一串数据表达每个线状地物的路径即可，将该线状地物经过的所有栅格的地址全部记录下来。仿照矢量数据组织的链状双重独立式编码，以弧段为记录单位。 弧标识号 起结点号 终结点号 中间点串（M1,M2,Z）? 20078 10025 10026 58,7749,435,92,4377,439… 线标识号 弧段标识号 …… …… 30031 20078，20079 30032 20092，20098，20099 …… …… 弧段的数据结构: 线状地物的数据结构: 矢栅一体化数据结构 当前第66页\共有88页\编于星期五\9点 3) 面状地物的数据结构 a ) 弧段文件 b）带指针的二维行程码 二维行程M码 属性值 0 0 5 4 8 0 16 4 30 8 31 4 32 0 37 8 40 0 44 8 46 0 47 8 叶结点的属性值 改为指向该地物的下一个子块的循环指针 二维行程M码 循环指针属性值 0 8 5 16 8 32 16 31 30 37 31 4（属性值） 32 40 37 44 40 46 44 47 46 0（属性值） 47 8（属性值） 边界弧段-----形状 面域 循环指针指向该地物下一个连续子块的地址码，并在最后指向该地物本身属性 共同表示 矢栅一体化数据结构 当前第67页\共有88页\编于星期五\9点 2）线性四叉树 记录叶结点的位置，深度（几次分割）和属性。 地址码（从根节点到叶节点的路径） 优点： ·存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。 ·线性四叉树可直接寻址，通过其坐标值直接计算其Morton码，而不用建立四叉树。 ·定位码容易存储和执行实现集合相加等组合操作。 栅格数据结构 当前第31页\共有88页\编于星期五\9点 四进制的Morton码 方法1： 四叉树从上而下（形成）（从整体开始） 由叶结点找Morton码。 A、分割一次，增加一位数字，大分割在前，小分割在后。所以，码的位数表示分割的次数。 B、每一个位均是不大于3的四进