第3章：空间数据结构.ppt

§1、栅格数据结构 §2、矢量数据结构 §3、两种数据结构的比较与转化 §4、其他数据结构 §4、 栅格数据结构 栅格数据表示的是二维表面上的地理数据的离散化数值。在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元相对应。因此，栅格数据的比例尺就是栅格(象元)的大小与地表相应单元的大小之比，当象元所表示的面积较大时，对长度、面积等的量测有较大影响。每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生属性方面的偏差。 2、栅格数据组织 组织方法 3、栅格结构的建立 （二）栅格系统的确定 2、? 栅格单元的尺寸 (三)栅格代码（属性值）的确定 4、栅格数据编码方法 二、栅格数据的压缩编码方式 1、链式编码 将栅格数据（线状地物面域边界）表示为矢量链的记录 1）首先定义一个3x3窗口，中间栅格的走向有8种可能，并将这8种可能0~7进行编码。 2）记下地物属性码和起点行、列后，进行追踪，得到矢量链. 具体应用时，一般从上到下，从左到右找起始点，属性非0的点，记下该地物的属性码后按顺时针方向找相邻的等值点，并按八个方向的编码记录，如遇不闭合的线段，结束返回找下一线段的起始点，为避免重复，记录过的栅格属性值赋为背景值0。 2、游程长度编码（变长编码）： 3、块码 ---- 游程编码向二维扩展 4.四叉树数据结构 其基本思想是将一幅栅格数据层或图像等分为四部分，逐块检查其格网属性值（或灰度）；如果某个子区的所有格网值都具有相同的值，则这个子区就不再继续分割，否则还要把这个子区再分割成四个子区 四叉树分解过程 从上而下的分割需要大量的运算，因为大量数据需要重复检查才能确定划分 。 采用从下而上的方法建立。检测方法如下。如果每相邻四个网格值相同则进行合并，逐次往上递归合并，直到符合四叉树的原则为止。这样重复计算较少，运算速度较快。 要求栅格数据的栅格单元数必须满足2n×2n ，对于非标准尺寸的图像需首先通过增加背景的方法将栅格数据扩充为2n×2n个单元，对不足的部分以0补足 。 四叉树结构按其编码的方法不同又分为常规四叉树和线性四叉树。 线性四叉树则只存贮最后叶结点的信息，包括叶结点的位置、深度和本结点的属性或灰度值。 线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。 （1）先将十进制的行列号转换成二进制数， （2）进行“位”运算操作，即行号和列号的二进制数两两交叉，得到以二进制数表示的MD码， （3）将其转换为十进制数。 五、四叉树编码 3、 编码方法 2）线性四叉树 （三）十进制的Morton码---MD （四）四叉树优缺点 4) 四叉树未能直接表示物体间的拓扑关系。 （二）矢量数据的获取方式 （三）矢量数据组织 以点为例： 二、矢量数据结构以编码方法 （二）索引式（树状） （三）双重独立式编码 （四）链状双重独立式编码--拓扑数据结构 链状双重独立式编码 特点 §3、 两种数据结构的比较与转化 矢量、栅格数据结构的选择 2、矢量数据结构向栅格数据结构的转换 1）点的变换 点落在那个网格中，这个点就属于那个网格元素，其行、列坐标由下式求出： 2）矢量线段的变换 两端点坐标（x1,y1),(x2,y2)，要确定直线经过的中间网格，只要确定中间行的y坐标，再求出这点的J值。 依同样的方法找到直线经过的每一网格，再用直线的属性值（特征值）去填充这些网格，完成直线的转换。 2）多边形数据的变换 步骤： （1）从数字化数据的第一点开始依次记录每一点左边面域的属性值（面域外为0，内为1） （2）对多边形的每一条边，按以上所述的线段栅格化的方法进行转换。 （3）节点处理，使节点的栅格值唯一准确。 （4）排序，从第一行起逐行按列的先后顺序排序。 （5）展开不栅格数据结构，完成由矢量数据向栅格数据的转换。 3、栅格数据结构向矢量数据结构的转换 1）基于图像数据的矢量化方法 （1）二值化，在最大与最小之间定义一个阈值T，大于T为1，小于T为为，得到一幅二值图。 （2）细化，消除线划横断面栅格数差异，使得每一线只保留其轴线或周围廓线位置的单个栅格的宽度。 （3）跟踪，将细化处理后的栅格数据，整理为从结点出发的线段或闭合的线条，并以矢量形式存储于特征栅格点中心的坐标。 1）基于再生栅格数据的矢量化方法 （1）边界跟踪。 （2）拓扑关系生成。 （3）去除多余点曲线圆滑。 §4、 其他数据结构 1、矢栅一体化数据结构 三、三个约定和细分格网法 四、一体化数据结构设计 2、线状地物的数据结构 3、面状地物的数据结构 用循环指针将同属于一个目标的叶结点链接起来 3）面文件 4、复杂地物的数据结构 2、镶嵌数据结构 1）