空间数据结构.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,,,*,地理信息系统原理,GIS,,,第二章 空间数据结构,,§2-1,地理实体及其描述,,,§2-2,栅格数据结构,,,§,2,-,3,矢量数据结构,,,§2-5,矢栅一体化数据结构,,,二、,地理实体的描述,,,,四、,实体间空间关系,,,一、,地理实体,,三、,实体的空间特征,,,一、图形表示,,二、数据组织,,四、栅格,数据,编码,,,三、栅格结构的建立,,§2-6,三维数据结构,,,§2-4,栅矢数据的比较,,,一、栅矢数据的比较,,二、栅矢数据的选择,,一、矢栅一体化概念,,三、一体化结构设计,,,二、,三个约定和细分格网法,,,二、八叉树结构,,一、概述,,三、四面体格网,,五、参数函数表示法,,四、三维边界表示法,,一、图形表示,,二、获取方式,,三、组织,,四、编码方式,1,,§2-1地理,实体及其描述,,第二章,GIS,数据结构,一、地理实体（空间实体）,---GIS,处理对象,,1,、定义,指自然界现象和社会经济事件中,不能再分割,的单元，它是一个具有,概括性，复杂性，相对性,的概念。

地理实体类别及实体内容的确定是从,具体需要,出发的，例如，在全国地图上由于比例尺很小，蚌埠就是一个点，这个点不能再分割，可以把蚌埠定为一个地理实体；在大比例尺的蚌埠市交通图上，蚌埠的许多房屋，街道都要表达出来，所以蚌埠必须再分割，不能作为一个地理实体，应将房屋，街道等作为研究的地理实体，由此可见，,GIS,中的空间实体是一个概括，复杂，相对的概念2,、理解,2,,,,,,,,,,1),描述的内容,,,3),数据类型,,,,,矢量、栅格、,TIN,（专用于地表或特殊造型）,,,,,,,RDBMS,属性表,----,采用,MIS,较成熟,,,,,,,,,空间元数据,,位置、形状、尺寸等,,,识别码（名称）实体的角色、功能、行为、实体的衍生信息,,,时间,,,测量方法、编码方法、空间参考系等,,空间特征：地理位置和空间关系,,,,属性特征,—,名称、等级、类别等,,,时间特征,2),基本特征,,4),数据结构,几何数据,（空间数据、图形数据）,,关系数据,—,实体间的邻接、关联、包含等相互关系,,,,属性数据,—,各种属性特征和时间特征,,,,元数据,,,,二、地理实体的描述1 空间数据,,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,以什么形式存储和处理,,,,,,3,,2、空间数据基本特征,,,4,,3、空间数据类型,1,）依据数据来源的不同分为,：,,,,2,）依据表示对象的不同分为,：,,地图数据,,地形数据,,属性数据,,元数据,,影象数据,5,,3、空间数据类型（续）,,6,,,三、实体的空间特征,,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,（一）空间维数：,有,0,，,1,，,2,，,3,维之分，点、线、面、体。

二）空间特征类型,（三）实体类型组合,地理实体维数可以改变,,点,---,面,,线（单线河）,---,面（双线河）,,1,、点状实体,,2,、线状实体,,3,、面状实体,,4,、体状实体,,7,,1、点状实体,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,点或节点、点状实体点,：有特定位置，维数为,0,的物体3,）内点：,用于负载多边形的属性，存在于多边形内4,）角点、节点,Vertex,：,,表示线段和弧段上的连接点2,）注记点,：用于定位注记1,）实体点,：用来代表一个实体返回,8,,2,、线状实体,特性：,,1,）实体长度,：,,从起点到终点的总长,,2,）弯曲度,：,,用于表示像道路拐弯时弯曲的程度3,）方向性,：,,如：水流方向，上游,—,下游，,,公路，单、双向之分§2-1,地理,实体及其描述,,第二章,GIS,数据结构,线,：具有相同属性的点的轨迹，线或折线，由一系列的有序坐标表示,,1,维：长度,线状实体包括,：,,线段，边界、链、弧段、网络等返回,9,,3,、面状实体（多边形）,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,面状实体的如下,特征,：,,1,）,面积与范围,,2,）,周长,,3,）,独立性或与其它地物相邻,,如中国及其周边国家,,4,）,内岛屿或锯齿状外形,：,,如岛屿的海岸线封闭所围成的区域。

5,）重叠性与非重叠性,：,,如学校的分区，菜市场的服务范围等都有可能出现交叉重叠现象，而一个城市的各个城区一般说来不会出现重叠面：对湖泊、岛屿、地块等一类现象的描述由,封闭曲线加内点,来表示2,维：长度、宽度,,返回,10,,,4、体状实体,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,返回,,体状实体,特征,：,,·,体积，如工程开控和填充的土方量·,每个二维平面的面积·,周长·,内岛·,含有弧立块或相邻块·,,断面图与剖面图体：用于描述三维空间中的现象与物体，它具有长度、宽度及高度等属性,,3,维：长度、宽度、高度,11,,,,（三）实体类型组合,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,,现实世界的各种现象比较复杂，往往由不同的空间单元组合而成，例如根据某些空间单元或几种空间单元的组合将空间问题表达出来，复杂实体由简单实体组合表达点、线、面两两之间组合表达复杂的空间问题：,,如：,线,—,面,,面,--,面,,,,,空间关系是,GIS,数据描述和表达的重要内容,，一方面它为,GIS,数据库的有效建立，空间查询，空间分析，辅助决策等提供了最基本的关系，另一方面有助于形成标准的,SQL,空间查询语言，便于空间特征的存储，提取，查询，更新等。

12,,线,—,面,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,返回,1,、,区域包含线,：计算区域内线的密度，某省的水系分布情况2,、,线通过区域,：公路上否通过某县3,、,线环绕区域,：区域边界，搜索左右区域名称，中国与哪些国家接壤4,、,线与区域分离,：距离13,,面,—,面,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,1,、,,包含,：岛,,,某省的湖泊分布返回,,,学校,菜场,3,、,,相交,：划分子区4,、,,相邻,：计算相邻边界性质和长度，公共连接边界5,、,分离,：计算距离2,、,,相合,：重叠，学校服务范围与菜场服务范围重叠区14,,四、,实体间空间关系,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,（一）空间关系类型,北,a,b,,,,1,、,,,顺序,空间关系,： （,方向,空间关系,）,,用上下左右、前后、东南西北等方向性名称来描述空间实体的顺序关系，算法复杂，至今没有很好的解决方法2,、,,度量空间关系,：实体间的距离关系,,1,）度量方法,a,、沿,真实的地球表面,进行,,,除与两点的地理坐标有关外，还与所通过路径的地形起伏有关。

b,、沿,地球旋转椭球体,的距离量算2,）,,距离类别,：,,欧氏距离（笛卡尔坐标系）、曼哈顿（出租车）距离、时间距离（纬度差）、大地测量距离（大地线）（沿地球大圆经过两个城市中心的距离）3,、,,拓扑空间关系,：,15,,（二）拓扑关系,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,1,、定义,：,,,拓扑关系,：图形保持连续状态下变形，但图形关系不变的性质拓扑变换,,（橡皮变换）,,非拓扑属性,（几何）,拓扑属性（,没发生变化的属性）,两点间距离,,一点指向另一点的方向,,弧段长度、区域周长、面积 等,,一个点在一条弧段的端点,,一条弧是一简单弧段（自身不相交）,,一个点在一个区域的边界上,,一个点在一个区域的内部/外部,,一个点在一个环的内/外部,,一个面是一个简单面,,一个面的连通性,面内任两点从一点,,可在面的内部走向另一点,1,、定义,2,、种类,3,、拓扑关系的表达,4,、意义,,将橡皮任意拉伸，压缩，但不能扭转或折叠16,,2、种类,,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,1,）关联性,： （,不同类,要素之间）结点与弧段：如,V9,与,L5,L6,L3,,多边形与弧段：,P2,与,L3,L5,L2,,P1,P2,P3,P4,P1,--,1,1,1,P2,1,--,1,0,P3,1,1,--,0,P4,1,0,0,--,2,）邻接性,：,(,同类,元素之间,),,多边形之间、结点之间。

邻接矩阵,,,重叠：,--,邻接：,1,不邻接：,0,17,,3）连通性：要素之间的通达关系,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,连通矩阵,：,,重叠：,--,连通：,1,不连通：,0,,V1,V2,V3…,V1,--,1,0,V2,1,--,1,V3,0,1,--,18,,4）方向性：,一条弧段的起点、终点确定了弧段的方向用于表达现实中的有向弧段，如城市道路单向，河流的流向等§2-1,地理,实体及其描述,,第二章,GIS,数据结构,5,）包含性,：指面状实体包含了哪些线、点或面状实体6,）区域定义,：多边形由一组封闭的线来定义7,）层次关系,：相同元素之间的等级关系，淮南市有各个区组成主要的,拓扑关系：,拓扑邻接、拓扑关联、拓扑包含,19,,拓扑关系具体可由,4,个关系表来表示：,,（,1,）,,面,--,链关系,： 面 构成面的弧段,,（,2,）,,链,--,结点关系,： 链 链两端的结点,,（,3,）,,结点,--,链关系,： 结点 通过该结点的链,\,,（,4,）,链,—,面关系,： 链 左面 右面,3、拓扑关系的表达,1,）拓扑关系能,清楚地反映,实体之间的,逻辑结构关系,，它比几何关系具有更大的稳定性，不随地图投影而变化。

2,）,有助于空间要素的查询,，利用拓扑关系可以解决许多实际问题如某县的邻接县，,--,面面相邻问题又如供水管网系统中某段水管破裂找关闭它的阀门，就需要查询该线（管道）与哪些点（阀门）关联3,）根据拓扑关系可,重建地理实体,§2-1,地理,实体及其描述,,第二章,GIS,数据结构,返回,4,、拓扑关系的意义,：,,,,,20,,,第二章,GIS,数据结构,返回,,空间数据结构：,适合于计算机系统,存储、管理和处理,的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述21,,§2-2,栅格数据结构,,第二章,GIS,数据结构,22,,,§2-2,栅格数据结构,,,第二章,GIS,数据结构,返回,,栅格结构用密集正方形（或三角形，多边形）将地理区域,划分,为网格阵列位置由行，列号定义，属性为栅格单元的值一、图形表示,,,,,,2,,,,,,,,,2,,,,,,,1,,,2,,,,,,,,,2,,,,3,3,,,,2,,,,3,3,3,,,,2,,,,3,3,3,,,2,,,,3,3,3,,,2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,栅格数据表示的是二维表面上的地理数据的,离散化,数值。

在栅格数据中，地表被分割为相互邻接、规则排列的地块，每个地块与一个象元相对应点,：由,单个栅格,表达线,：由沿线走向有相同属性取值的,一组相邻栅格,表达面,：由沿线走向有相同属性取值的,一片栅格,表达栅格数据的,比例尺,就是,栅格,(,象元,),的大小与地表相应单元的大小之比,，当象元所表示的面积较大时，对长度、面积等的量测有较大影响每个象元的属性是地表相应区域内地理数据的近似值，因而有可能产生,属性方面的偏差,3,,,,,,,,,,3,,,,,,,,,,3,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,23,,二、,栅格数据,组织,§2-2,栅格数据结构,,第二章,GIS,数据结构,返回,——,针对,一个栅格单元对应多个属性值的多层栅格文件,空间数据库,,2,2,2,2,2,,a,a,a,a,a,2,2,土壤,植被,组织方法,,,24,,,组织方法,§2-2,栅格数据结构,,第二章,GIS,数据结构,返回,方法,c,：,以层为基础，每层内以多边形为序记录多边形的属性值和多边形内各象元的坐标,节约用于存储属性的空间将同一属性的制图单元的,n,个象元的属性只记录一次，便于地图分析和制图处理。

方法,a,：,以象元为记录序列，不同层上同一象元位置上的各属性值表示为一个列数组N,层中,只记录一层的象元位置，,节约大量存储空间，,栅格个数很多方法,b,：,以层为记录顺序，每层每个象元的位置、属性一一记录，,结构最简单，但浪费存储25,,三、栅格结构的建立,§2-2,栅格数据结构,,第二章,GIS,数据结构,返回,1,、,,手工获取,，专题图上划分均匀网格，逐个决定其网格代码一）建立途径,,,2,、,扫描仪扫描,专题图的图像数据,{,行、列、颜色（灰度）,},，定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据3,、,,由矢量数据转换而来,4,、,,遥感影像数据，,对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列5,、,,格网,DEM,数据,，当属性值为地面高程，则为格网,DEM,，通过,DEM,内插得到26,,（二）栅格系统的确定,§2-2,栅格数据结构,,第二章,GIS,数据结构,栅格编码一般用于区域性,GIS,，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的,起始坐标应与国家基本比例尺地形图公里网的交点相一致,，并分别采用,公里网的纵横坐标轴作为栅格系统的坐标轴,。

2,,,,,,,,,2,,,,,,,1,,,2,,,,,,,,,2,,,,3,3,,,,2,,,,3,3,3,,,,2,,,,3,3,3,,,2,,,,3,3,3,,,2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构,(,矢、栅,),都应在统一的,坐标系统,下，而坐标系的确定实质是坐标系原点和坐标轴的确定1,、坐标系统的确定,27,,2,）方法,：用保证最小多边形的精度标准来确定尺寸经验公式：,,,,,h,为栅格单元边长,,,Ai,为区域所有多边形的面积2、,,栅格单元尺寸的确定,§2-2,栅格数据结构,,第二章,GIS,数据结构,1,）原则,：应能,有效地逼近空间对象的分布特征，又减少数据的冗余度,格网太大,，忽略较小图斑，信息丢失格网越小,，分辨率愈高，适合表示复杂地物，但数据量愈大（按分辨率的平方指数增加），计算机成本越高，处理速度越慢28,,（三）栅格代码（属性值）的确定,§2-2,栅格数据结构,,第二章,GIS,数据结构,,当一个栅格单元内有多个可选属性值时，按一定方法来确定栅格属性值A,B,,,,,b,a,,3,、,长度占优法,——,每个栅格单元的值由该栅格中线段最长的实体的属性来确定。

4,、重要性法,：根据栅格内不同地物的重要性，选取最重要的地物类型的属性作为栅格单元的属性值沙漠地区：水,,2,、面积占优法,：栅格单元属性值为面积最大者，常用于分类较细，地理类别图斑较小时1,、中心点法,：取位于栅格中心的属性值为该栅格的属性值2,,,,1,,29,,,,,,,,,,,,,,,,,,四、栅格数据编码方法,§2-2,栅格数据结构,,第二章,GIS,数据结构,,1,、直接栅格编码：,A A A A,,A B B B,,A A B B,,A A B B,,,数据压缩,是将数据表示成更紧凑的格式以减少存储空间的一项技术,分为：,,无损压缩,：在编码过程中信息没有丢失，经过解码可恢复原有的信息,---,信息保持编码,有损压缩,：为最大限度压缩数据，在编码中损失一些认为不太重要的信息，解码后，这部分信息无法恢复信息不保持编码,编码方法：,将栅格数据看作一个数据矩阵，,逐行记录代码数据1,）每行都从左到右记录；,,2,）奇数行从左到右，偶数行从右到左；,AAAA,BBBA,AABB,BBAA,,特点,：,最直观、最基本的网格存贮结构，没有进行任何压缩数据处理,。

数据压缩：,栅格数据量大，格网数多，由于地理数据往往有较强的相关性，即相邻象元的值往往是相同的所以，出现了各种栅格数据压缩方法30,,,,,,,,,,,,,,,,,,2、游程长度编码,：,§2-2,栅格数据结构,,第二章,GIS,数据结构,编码方法：,按,行,扫描，将相邻属性值相同的像元合并，记录代码的重复个数属性码，长度，行号（可不要）,,长度：连续相同码值的栅格个数特点：,对于游程长度编码，区域越大，数据的相关性越强，则压缩越大，,适用于类型区域面积较大的专题图,，而不适合于类型连续变化或类别区域分散的分类图（压缩比与图的复杂程度成反比）这种编码在,栅格加密时，数据量不会明显增加，压缩率高，并最大限度地保留原始栅格结构，编码解码运算简单，且易于检索，叠加，合并等操作,，这种编码应用广泛A A A A,,A B B B,,A A B B,,A A B B,,,,行与行间断编码：,A4,A1B3,A2B2,A2B2,行与行不间断编码：,A5B3A2B2A2B2,31,,3、块码,----,游程编码向二维扩展,§2-2,栅格数据结构,,第二章,GIS,数据结构,编码方法：,采用,方形区域,作为记录单元，每个记录单元包括相邻的若干栅格,。

数据对组成,：（初始行、初始列，半径，属性值）,特点,：,,具有,可变分辨率,，即当属性变化小时图块大，对于大块图斑记录单元大，分辨率低，压缩比高小块图斑记录单元小，分辨率高，压缩比低,,所以，与行程编码类似，随图形复杂程度的提高而降低分辩率依次扫描，编过的不重复1 2 3 4 5 6 7 8,,1 0 4 4 7 7 7 7 7,,2 4 4 4 4 4 7 7 7,,3 4 4 4 4 8 8 7 7,,4 0 0 4 8 8 8 7 7,,5 0 0 8 8 8 8 7 8,,6 0 0 0 8 8 8 8 8,,7 0 0 0 0 8 8 8 8,,8 0 0 0 0 0 8 8 8,,,,,,,,,,,,,,,,,,,,,（,1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),，,(1,6,2,7),(1,8,1,7)……,,,,,,,,,,,,,,,32,,4、链式编码、Freeman 链码、边界链码,§2-2,栅格数据结构,,第二章,GIS,数据结构,1,）首先定义一个,3x3,窗口，中间栅格的走向有,8,种可能，并将这,8,种可能,0~7,进行编码。

2,）记下地物属性码和起点行、列后，进行追踪，得到矢量链,.,编码方法：,将栅格数据（线状地物面域边界）表示为,矢量链,的记录,链式编码表,,,,a,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,a,a,a,a,a,a,b,属性码,起点行,起点列,链码,a,1,4,556656,b,3,7,576654323…,,优点,：链码可有效地存贮压缩栅格数据，便于面积、长度、转折方向和边界、线段凹凸度的计算缺点,：不易做边界合并，插入操作、编辑较困难（对局部修改将改变整体结构）区域空间分析困难，相邻区域边界被重复存储33,,A,A,A,A,A,B,B,B,A,A,B,B,A,A,B,B,,,,,,,,,,,5、四叉树编码,§2-2,栅格数据结构,,第二章,GIS,数据结构,（,1,）、  基本思想：,,将,2,n,×,2,n,象元组成的图像,,按四个象限进行递归分割，,,并判断属性是否单一， 单一：不分不单一：递归分割最后得到一颗四分叉的倒向树一）四叉树概述,：,0,1,2,3,,一种,可变分辨率,的,非均匀网格,系统。

是最有效的栅格数据压缩编码方法之一,,（,2,）、,,四叉树的树形表示,：,,用一倒立树表示这种分割和分割结果根,：整个区域,,高,：深度、分几级，几次分割,,叶,：不能再分割的块,,树叉,：还需分割的块,,每个树叉均有,4,个分叉，叫四叉树象限编码,34,,（3）,、,,编码方法,§2-2,栅格数据结构,,第二章,GIS,数据结构,1,）常规四叉树,指针不仅,增加了数据的存储量,，还增加了操作的,复杂性,：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来所以，,常规四叉树并不广泛用于存储数据,，其价值在于建立索引文件，进行数据检索记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，,,每个结点需要,6,个变量：,,父结点指针、四个子结点的指针和本结点的属性值,35,,2）线性四叉树,§2-2,栅格数据结构,,第二章,GIS,数据结构,记录叶结点的,位置，深度,（几次分割）和属性地址码（定位码、,Morton,码） 四进制、十进制,,优点,：,,·,存贮量小，只对叶结点编码，节省了大量中间结点的存储，地址码隐含着结点的分割路径和分割次数。

·,线性四叉树可直接寻址，通过其坐标值直接计算其,Morton,码，而不用建立四叉树·,定位码容易存储和执行实现集合相加等组合操作36,,（,二,）四叉树优缺点,§2-2,栅格数据结构,,第二章,GIS,数据结构,优点,：,缺点：,1,）,对于团块图像，四叉树表示法占用空间比网络法要少得多，四叉树表示法基本上是一种,非冗余表示法,2,）,四叉树具有,可变分辨率或多重分辩率,的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别适用于处理分布不均匀的块状空间数据，但不适用于连续表面（如地形）或线状地物1),矢,/,栅正反变换还不理想3),,四叉树虽可修改，但很费事,2),,建立四叉树耗费机时很多37,,4),,四叉树,未能直接,表示物体间的拓扑关系§2-2,栅格数据结构,,第二章,GIS,数据结构,返回,5),,与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫,滑动变异,,例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别，,,A 0,A 1,A 4,A 5,A 2,,B 3,B 6,B 7,A 8,A 9,B 12,B 13,A 10,A 11,B 14,B 15,,,,,,,,,,,,,,,,,,,,A,A,A,A,,,,,A,B,B,B,,,,,A,A,B,B,,,,,A,A,B,B,,,,,,,,,,,,,,,,,,6),,一个,物体,的图像,在构成四叉树时会被分割到若干个象限中，使它,失去了内在的相关性,。

A,A,A,A,,,,,A,B,B,B,,,,,A,A,B,B,,,,,A,A,B,B,,,,,,,,,,,,,,,,,,,,,38,,。