第4章空间数据表达.ppt

第四章第四章 空间数据空间数据的表达的表达本章主要介绍地理现象空间实体类型空间数据表达方法（数据结构）1.地理系统与地理现象2.空间对象及其定义3.空间对象关系4.空间数据的矢量表达5.空间数据的栅格表达6.混合数据结构与一体化数据结构7.镶嵌数据结构8.四叉数数据结构9.超图数据结构本章重点与作业本章内容：本章内容：v1.1 1.1 地理系统地理系统v1.2 1.2 地理现象地理现象1.1.地理系统与地理现象地理系统与地理现象地理系统地理系统q地理系统是一个开放的复杂系统地理系统主要涉及地球表层空间，包括：岩石圈、水圈、生物圈、大气圈和电离层GIS目前主要涉及的范围主要为岩石圈和大气圈之间v1.1 1.1 地理系统地理系统电离层电离层大气圈大气圈水圈水圈生物圈生物圈岩石圈岩石圈地理系统、GIS所涉及的地理系统范围GISGIS涉及的范围涉及的范围q地理系统是开放系统和其他系统有关联、有交往，既有能量物质的交流，又有信息的交流，例如地球表层接受太阳光和电磁波、辐射红外线受天体运动产生的外力作用q地理系统是复杂系统由成千上万个子系统组成人、植物、动物、地下矿产、山山水水地理地理系统的两个方面地理系统的两个方面地理系统主要涉及地球表层空间，包括：岩石圈、水圈、生物圈、大气圈和电离层GIS目前主要涉及的范围主要为岩石圈和大气圈之间地理系统的内部构成及其与外部系统的联系地理系统地理系统社会经济环境系统社会经济环境系统人口、工业、农业、交通、人口、工业、农业、交通、建筑、商业、科学、教育、建筑、商业、科学、教育、卫生、金融卫生、金融天体系统天体系统地球内部系统地球内部系统自然环境系统自然环境系统地貌、土壤、气候、土地利用、地貌、土壤、气候、土地利用、水文、生物、海洋水文、生物、海洋人地关系系统人地关系系统q地理系统中的各种要素特征都与地理空间位置有关q地理科学的任务：综合研究地理系统中的生物圈、水圈、岩石圈三大要素的空间分布规律及其相互之间关系和相互影响涉及地球表层空间，包括：岩石圈、水圈、生物圈、大气圈和电离层GIS目前主要涉及的范围主要为岩石圈和大气圈之间地理现象的抽象过程地理现象的抽象过程地理系统主要涉及地球表层空间，包括：岩石圈、水圈、生物圈、大气圈和电离层GIS目前主要涉及的范围主要为岩石圈和大气圈之间v1.2 1.2 地理现象地理现象空间数据空间数据地图遥感影像特征特征关系关系行为行为观察观察测量：位置测量：位置编码：属性编码：属性建立关系：建立关系：表达表达 现实世界选择选择分析分析抽象抽象综合综合描述地理现象的四种几何类型描述地理现象的四种几何类型q呈点状分布的地理现象人工：城镇、乡村居民点、交通枢纽、车站、工厂、学校自然：火山口、山峰、地震震中、温泉口可以用一个点位置来描述；是一个相对概念，当考虑比例尺较大时，可能表示成面q呈线状分布的地理现象自然：河流、海岸人工：铁路、公路、地下管线、行政边界有单线、双线和网状之分；可以用一线状坐标串或封闭坐标串表示（狭长的水面）q呈面状分布的地理现象人工：水库、建筑物、机场自然：土壤、耕地、森林、草原、沙漠、湖泊呈大范围的连续分布；用封闭坐标串表示q呈体状分布的地理现象从三维角度观测自然：云、水体、矿体人工：高层建筑物、地铁站特点是向三维方向扩展，但通常处理成二维平面形式；要正确表示成体的形式，必须采用三维模型来描述2.2.空间对象及其定义空间对象及其定义空间实体空间实体(Spatial Entity)(Spatial Entity)是地理空间中不可再分的最小单元，它不仅反映事物和现象的本质内容，而且反映它们在地理空间中的位置、分布状况以及它们之间的相互关系空间实体具有：属性、空间位置、空间关系和时间四种特征空间对象（空间对象（Spatial ObjectSpatial Object）也称空间目标，它是对空间现象进行抽象得到的结果,是空间实体的物理表示,如q控制点、池塘、活树篱笆空间对象的定义与数据模型和数据结构有关，不同的系统有所不同美国空间数据交换标准（STDS）是目前为止对空间对象定义最为完整的标准1 1）空间实体的几个概念）空间实体的几个概念q目标：目标：也称空间对象，是空间实体的物理表示q实实体体类类型型：即实体的几何类型，有点、线、面、体之分q实实体体属属性性：对实体特征的描述，属性有属性值的概念并有等级之分，如公路实体有公路等级属性值，可以分为一级、二级公路q实实体体要要素素：实体是点、线、面、体多种要素的复杂组合，是那些基本的、实际的、不可再分的空间单元（元素）v2.1 2.1 空间对象描述空间对象描述2 2）空间实体的描述）空间实体的描述q对空间实体的描述有5种内容，即：识别码、位置、实体特征、实体的角色、行为或功能以及实体的空间特性q识识别别码码：用于区别同类而又不同的实体，通常用对象标识码（OID）来表示，如同为一级公路类型的不同的公路q位位置置：可用坐标描述，也可用其它形式（如邮政编码）q空空间间特特征征：也是位置信息的一种，如维数、类型及实体的组合q实实体体的的行行为为和和功功能能：是指在数据采集过程中不仅要重视实体的静态描述，还要收集那些动态的变化，如岛屿的侵蚀、水体污染的扩散、建筑的变形等q实体的衍生信息：实体的衍生信息：如一个实体有许多个名称q实实体体的的维维数数：分零维、一维、二维、三维、甚至四维（三维+时间）信息分类实例空间单元的类型1 1）零维空间对象的定义）零维空间对象的定义零零维维对对象象即点状空间实体，由一组坐标（x,y,z）说明其位置可以分为：实体点：用来代表一个实体,如塔、浮标标识点（注记点）：用于定位地图或插图的文本信息（注记）面标识点：用于负载多边形的属性，存在于多边形内节点：表示线（或弧）的终点和起点顶点：表示线段和弧段的内部点v2.2 2.2 空间对象定义空间对象定义2 2）一维空间对象的定义）一维空间对象的定义一一维维对对象象即线状空间实体，由一列有序坐标串表示，有如下特性：实体长度：从起点到终点的总长弯曲度：用于表示像道路拐弯时弯曲的程度方向性：河流方向是从上游到下游，公路则有单向与双向之分q一维对象可以分为：线段：两点之间的直线弦列：相互连接无分支的线段弧：曲线轨迹，可以用数学函数定义拓扑连线：两个节点之间的拓扑连接，由结点的顺序确定其方向链：非相交的线段或弧的无分支而有向序列，可以分为：全链、面链、网链全链：可以显式定位左右多边形和始终端节点的链面链：可以显式定位左右多边形、但不能定位始终端节点的链网链：可以显式定位始终端节点、但不能定位左右多边形的链环：是一个由不相交的链或弦列和（或）弧的闭合系列，它只表示一个封闭的边界，但不表示封闭内的面积G-环：边界系列无方向GT-环：边界系列有方向，由多条链组成线状实体类型线状实体类型3 3）二维空间对象的定义）二维空间对象的定义二维对象即面状空间实体，如对湖泊、岛屿、地块等，在数据库中由一封闭曲线加内点来表示，有如下空间特性：面积范围周长独立性或与其它的地物相邻，如中国及其周边国家内岛或锯齿状外形重叠性与非重叠性q二维对象可以分为：内面：不包括其边界的面G-多边形：由一个内面、一个外G-环和零个或多个不相交的内G-环组成的面GT-多边形：由GT-环为边界定义的多边形，也可以由多个链直接定义广义多边形：定义为GT-多边形覆盖的面的周边以外的面虚多边形：为二维拓扑面的一部分，以其它的GT-多边形为界，但其它方面有与广义多边形相同的特性像元：是一个二维的图素，是不可再分的图像元素格网单元：一个网单元的二维对象面状实体类型面状实体类型4 4）三维空间对象的定义）三维空间对象的定义三维对象即体状空间实体，是三维空间中的现象与物体，有如下空间特性：长度、宽度及高度体积，如工程开掘和填充的土方量每个二维平面的面积、周长内岛或锯齿状外形含有孤立块或相邻块q三维对象可以分为：体元：方形实体，是三维实体中不可再分割的元素标识体元：用于标识一个三维空间，类似于多边形中的标识点三维组合空间目标：由二维空间目标组合（房屋是由多个面组合而成）、也可以有三维体元构成体空间：体状实体类型体状实体类型5 5）聚合空间对象的定义）聚合空间对象的定义q现实世界的各种现象比较复杂，往往由不同的空间单元组合而成，例如：根据某些空间单元，可以将空间问题表达出来一个特殊任务有时需要几种空间单元来描述复杂实体有可能由不同维数和类型的空间单元组合而成某一类型的空间单元组合形成一个新的类型或一个复合实例某一类型的空间实体或以转换为另一类型某些空间实体具有二重性，也就是说，由不同的维数组合而成q聚合空间对象可以分为：格网：某种面的规则（矩形、三角形）或接近规则的镶拼图像：灰度或彩色像元集合层：表示某一种专题的实体（对象）或在众多空间对象中具有公共属性或属性值的空间对象的集合，如道路层、水系层、植被层栅格：同一类型网格或图像的一系列覆盖层图形：相互关联的零维、一维或二维对象的集合，可以分为：平面图形、二维拓扑面、网络平面图形：组成图形的节点、拓扑连线或链对象在平面上的图形二维拓扑面：指一个平面图形及相关联的二维对象网络：没有二维对象的图形，由节点、拓扑连线组成，它们可以不在一个平面上图形遵循的原则：链有一对有序节点，可以重合一个节点可以对应多条链链除在节点外不能相交空空间间（对对象象）关关系系是指地理实体之间存在的与空间特性有关的关系，如度量关系、方向关系、顺序关系、拓扑关系、相似关系、相关关系等(吴立新，2003)有些学者认为空空间间关关系系主主要要包包括括拓扑关系、方位关系和度量关系三种基本类型，其中空间拓扑关系是最重要的空间关系(王家耀，2001)空间对象描述包括：空间对象描述包括：几何位置、对象之间的空间关系几几何何位位置置：采用解析几何方法，如坐标、角度、方向、距离、周长、面积空空间间关关系系：采用拓扑几何来描述，如相邻、相离、相交、包含、重合等4.4.空间对象关系空间对象关系空空间间拓拓扑扑关关系系是指空间对象在拓扑变换(旋转、平移、缩放等)下保持不变的空间关系，即拓扑不变量，如空间目标的相邻和连通关系几何结构相差较大的图形，它们的拓扑结构可能相同结点拓扑关系1 1）点、线、面空间对象之间的五组关系表达）点、线、面空间对象之间的五组关系表达 邻接、相交、相离、包含、重合2 2）点线面体之间）点线面体之间1212种基本空间关系来表达种基本空间关系来表达相离（disjoint）、相等（equal）、相接（touch）相交（cross）、包含于（in）、包含（contain）交叠（overlap）、覆盖（cover）、被覆盖（covered by）、进入（enter）、穿越（pass）被穿越（pass by）线-线之间的7种空间关系面-面之间的10种空间关系面-体之间的8种空间关系4.4.空间对象的矢量表达空间对象的矢量表达1 1）有关概念）有关概念q空间对象的计算机表达的主要信息包括：空间位置、拓扑关系和属性信息q空间数据表达的主要形式：基于矢量的表达（矢量数据模型或实体模型）基于栅格的表达（栅格数据模型或场模型）q空间数据模型是对客观世界现象或实体的概念性描述 q数据结构是空间数据模型的实现手段，是数据模型的简化，强调其在计算机中的编码、存储与表现方法 q栅格数据模型采用栅格数据结构来描述，是基于位置的数据结构，它采用像元阵列来描述空间对象，每个像元的行列号确定位置，用像元值表示空间对象的类型、等级等特征（下一节详细介绍）q矢量数据模型采用矢量数据结构来描述，它是基于实体的数据结构，它通过记录空间对象的坐标（x,y,z）及空间关系来表达空间对象的位置q矢量数据结构应该表达内容：矢量数据自身的存储和管理几何数据和属性数据的联系空间对象的空间关系（拓扑关系）q空间关系表达空间关系表达=信息结构+操作q空间关系异常复杂，不可能在信息结构中存储所有的关系（数据量大、不便维护、难以保证关系的唯一性），而是有选择地预先记录部分关系，其它关系则根据操作来即时完成，例如MapInfo、MGE、ARCView不存储空间关系，要得到空间关系需要进行即时操作计算ARC/INFO、System9、TIGER文件等仅存储空间对象的邻接关系，要的到其它关系还需要进一步的操作计算2 2）矢量数据结构的基本元素）矢量数据结构的基本元素q点点实实体体除除存存储储点点实实体体的的x x，y y坐坐标标外外还还应应存存储储其其它它一一些些与与实实体体有有关关的的数数据据来来描描述述点点实实体体的的类类型型、制制图符号和显示要求图符号和显示要求q线实体矢量数据结构的基本内容包括：线实体矢量数据结构的基本内容包括：唯一唯一标识标识码码,线标识码线标识码,起始点起始点,终终止点止点,坐坐标标点点对对系列系列,显显示信息示信息,非几何信息非几何信息q多边形数据结构不但表示位置和属性，更重要的多边形数据结构不但表示位置和属性，更重要的 是能表达区域的是能表达区域的 拓扑特征（形状、邻域或层次拓扑特征（形状、邻域或层次结构）结构）3 3）无拓扑关系的矢量数据模型）无拓扑关系的矢量数据模型q也称面条数据模型（Spaghetti），仅记录空间对象的位置坐标和属性信息、不记录拓扑关系q存储方式独立存储：空间对象位置直接跟随空间对象点位字典：点坐标独立存储，线、面由点号组成q特点无拓扑关系，主要用于显示、输出及一般查询公共边重复存储，存在数据冗余，难以保证数据独立性和一致性多边形分解和合并不易进行，邻域处理较复杂处理嵌套多边形比较麻烦q适用范围制图及一般查询，不适合复杂的空间分析点号XY1112223344n5566标识码标识码属性属性空间对象编码唯一连接几何和属性数据数据库独立编码点:(x,y)线:(x1,y1),(x2,y2),(xn,yn)面:(x1,y1),(x2,y2),(x1,y1)点位字典点:点号文件线:点号串面:点号串几何几何 位置位置面条数据模型例如：1234567AB多边形编码坐标At1233,15,2Bt1243,12,3点号坐标1234563,15,24,61,5.50.5,1.52,3多边形编码点号串ABT123t1241,2,3,4,7,6,11,6,7,4,5,1点位字典独立编码MapInfo的文件格式及数据关联机制 4 4）拓扑数据模型）拓扑数据模型q不仅表达空间对象的几何位置和属性，还表示空间关系q表达对象：主要点、线、面之间的关联拓扑关系q表达方式全显式表达部分显式表达 q全显式表达：指结点、弧段、面块之间的所有关联拓扑关系都用关系表显式地表达出来N1B2N2N4N3B3B4B1A1A2A6A5A4A3A7A8N5面-弧拓扑面弧段弧-点拓扑弧起点弧-面拓扑弧左面点-弧拓扑点弧段终点右面面-弧拓扑面弧段弧-点拓扑弧起点弧-面拓扑弧左面点-弧拓扑点弧段终点右面弧-点-面拓扑弧起点终点左面右面A8B1B2B3B4A1A2A3A4A5A6A7N1N2N3N4N5M面弧点拓扑数据结构举例不规则三角网数据结构X-Y Coordinatesnode#coordinates12311.x1,y1x2,y2x3,y3.x11,y11Z Coordinatesnode#z_value12311.z1.z2z3z111236587911104ABCDEFGHIJKLMNEDGESadjacentABCDEFGHIJKLMNB,KA,C,LB,DC,E,LD,FE,GF,H,MG,IH,J,NI,KA,J,NB,D,MG,L,NI,K,MNODESnode#ABCDEFGHIJKLMN1,6,71,7,81,2,82,8,92,3,93,4,94,9,104,5,105,10,115,6,116,7,117,8,97,9,107,10,11q部分显式表达：仅表示结点、弧段、面块之间部分拓扑关系，它是全显式表达的子集q例如，System9：面-弧表、弧-点表 DIME：弧-点表、弧-面表q目前，商用GIS还没有超出全显式表达中四个表格的拓扑关系，如美国人口调查局1990年的TIGER(Topologically Integrated Geographic Encoding and Referencing)文件 q表格中的变长记录（弧段内点、组成面的弧段）的物理实现方法串行指针、直接存储变长记录例1：美国的计算机图形及空间分析实验室提出的POLYVERT数据结构和TIGER文件采用了串行指针来解决弧段变长记录问题例2：ARC/INFO、Geostar等软件采取了直接存储变长记录的方法，使数据结构变得简单得多ARC/INFO的矢量数据模型q拓扑数据模型的特点：数据结构紧凑、数据冗余小，拓扑关系明晰使得拓扑查询、拓扑分析效率高对单个地理实体的操作效率低、难以表达复杂的地理实体、局部更新困难q拓扑关系与数据共享建立拓扑关系比较麻烦但能解决好数据共享问题，尤其是在数据采集和图形编辑是，为维护数据的一致性提供了方便拓扑:移动结点无拓扑:移动结点q是否需要拓扑结构？应考虑的因素：是否需要拓扑结构？应考虑的因素：应用目的 制图或一般查询，可不要拓扑结构 空间分析，则应建立拓扑关系 服务对象和系统数据结构 面状目标：面-弧、弧-面 网络目标：点-弧、弧-点5 5）属性数据表达与组织）属性数据表达与组织q属性特征类型 类别特征：是什么 说明信息：解决两个同类目标的不同特征问题q属性特征表达 类别特征：类型编码 说明信息：属性数据结构和表格q属性表的属性项（内容）取决于用户，如宗地属性表、公路属性表q图形数据和属性数据的连接通过目标识别符（OID）或内部记 录号实现点状对象目标标识目标标识地物编码坐 标关联的线目标精度控制点等级测量单位测量年限线状对象目标标识目标标识地物编码坐 标串起点、终点、左面、右面路面材料等级修建时间宽度管养单位面状对象目标标识目标标识地物编码边界目标号建筑日期所有者建筑面积建筑单位结构空间对象地物编码地物名称制图颜色几何类型制图符号编码属性表名地物类型特征与制图属性ARC/INFO通过Id来建立图形和属性数据之间的联系5.5.空间对象的栅格表达空间对象的栅格表达1 1）栅格数据的概念）栅格数据的概念q栅格数据结构是基于位置的数据结构，它采用像元阵列来描述空间对象，每个像元的行列号确定位置，用像元值表示空间对象的类型、等级等特征q栅格数据是二维表面上地理数据的离散量化值（是地理数据的近似值）q每个栅格单元只能存在一个值，因此像元值是近似值q像元的大小对长度、面积等度量的量测有较大的影响栅格数据的近似性（偏差）栅格数据的近似性（偏差）abc345abcac距离:7/4 (5)面积:7 (6)几何偏差属性偏差矢量栅格2 2）空间对象的栅格数据结构表示）空间对象的栅格数据结构表示点：为一个像元线：在一定方向上连接成串的相邻像元集合面：聚集在一起的相邻像元集合q栅格数据的获取方式遥感数据图片扫描数据矢量数据转换手工方式点线面3 3）栅格数据结构）栅格数据结构坐标系与描述参数坐标系与描述参数Y：列X：行西南角格网坐标（XWS，YWS）格网分辨率格网方向4 4）栅格数据结构）栅格数据结构单元值确定单元值确定CAB百分比法面积占优重要性中心点法A连续分布地理要素C具有特殊意义的较小地物A分类较细、地物斑块较小ABq栅格数据可以用平面笛卡儿空间来描述，但一个平面笛卡儿空间只能具有一个属性数据，q当同一像元要表示多种地理属性时，则需要多个笛卡儿平面来描述，每个笛卡儿平面表示一种地理属性或同一属性的不同特征，这个平面就是“层”q每一层对应一个栅格文件，例如对于某个区域来说，用栅格数据来描述其土壤、森林覆盖类型时，就要进行分层处理，并分别存贮为土壤和森林数据文件5 5）栅格数据结构）栅格数据结构层的概念层的概念q栅格数据的组织方法有三种：方法一：方法一：以像元为记录的序列，不同层上同一像元位置上的不同属性值表示为一个列数组节省存储空间（像元坐标空间）6 6）栅格数据的组织方法）栅格数据的组织方法栅格数据文件像元1X坐标Y坐标层2属性值层1属性值层n属性值像元2像元n方法二：方法二：以层为基础，每一层记录后再记录下一层结构简单、处理方便、存储量大栅格数据文件层1像元1层2X,Y,属性值像元2X,Y,属性值像元nX,Y,属性值层n栅格数据文件层1多边形1层2属性值像元1坐标多边形N像元n坐标层n方法三：方法三：以层为基础，但每一层则以多边形为序记录多边形的属性值和充满多边形的各象元的坐标节省属性的存储空间7 7）矢量栅格数据比较）矢量栅格数据比较矢量数据优点：表示地理数据的精度较高严密的数据结构，数据量小完整的描述空间关系图形输出精确美观图形数据和属性数据的恢复、更新、综合都能实现面向目标，不仅能表达属性，而且能方便的记录每个目标的具体属性信息缺点：数据结构复杂矢量叠置较为复杂数学模拟比较困难技术复杂，特别是软硬件栅格数据优点：数据结构简单空间数据的叠置和组合方便各类空间分析很易于进行数学模拟方便缺点：图形数据量大用大像元减少数据量时，精度和信息量受损地图输出不美观难以建立网络连接关系投影变换比较费时8)8)数据结构选择原则数据结构选择原则q要素还是位置？q可获取的数据q定位要素的必要精度q需要什么类型的要素q需要什么类型的拓扑关联q所需空间分析类型q生产地图类型9 9）栅格数据结构的编码方法）栅格数据结构的编码方法分辨率与存储单元示意图分辨率与存储单元示意图 (1)(1)在高分辨率的情况下将占据更多的像元或存储单元；在高分辨率的情况下将占据更多的像元或存储单元；(2)(2)栅格模型是通过同样颜色或灰度像元来表达具有相同属栅格模型是通过同样颜色或灰度像元来表达具有相同属性的面状区域的。因此有许多栅格单元或像元与其邻近的若性的面状区域的。因此有许多栅格单元或像元与其邻近的若干像元都具有相同的属性值。为了节省存储空间，对栅格数干像元都具有相同的属性值。为了节省存储空间，对栅格数据进行压缩。下面，将介绍四种常用的数据压缩方法。据进行压缩。下面，将介绍四种常用的数据压缩方法。数据结构由初始位置（行、列号）和半径，加上记录单位的代码组成。对下一图像的块码编码如下：(1,1,1,0)，(1,2,2,4)，(1,4,1,7)6.6.混合数据结构与一体化数据结构混合数据结构与一体化数据结构矢量数据结构的基本逻辑单位是空间实体，它们的组织是按实体的标识（位置）显式地存储，特点是可以通过给定唯一的对象标识来确定每个实体的位置，便于空间查询与分析栅格数据的基本逻辑单位是实体的空间位置，并以位置属性来显示存储，便于叠置分析矢量数据与栅格数据的结合有助于发挥各自的优势，其方式有两种：q混合数据结构q一体化数据结构 q方式一：方式一：矢量和栅格数据不作任何特殊处理，它们各自按自己的数据结构存储，只是需要是将它们调入内存，进行统一的显示、查询和分析。例如遥感图像或扫描的栅格地图作为矢量地图的一个背景层 1 1）矢量栅格混合数据结构）矢量栅格混合数据结构q方式二：方式二：Peuauet于1981年模型，是矢量于栅格数据结构的组合，它同时兼顾矢量和栅格数据的特点，基本逻辑单位单元是条带，每条条带宽度固定，每条条带包含栅格成分和矢量成分，每条条带扫描Y值最小的栅格行，作为该条带的索引，并记录在该行中每根线条的标识符和交点的坐标，条带中其余部分按矢量数据格式进行记录，记录顺序按交点坐标的 X增大方向排列q该数据结构的理论基础是多级格网方法、三个基本约定和线性四叉树编码q多级格网方法是将格网划分成多级格网：粗格网、基本格网和细分格网粗格网用于建立空间索引基本格网于通常的栅格划分原则一致，为基本格网的的 大小细分格网，当基本格网精度比较低时，为了提高栅格数据的表达精度，需要对有点线通过的基本格网进行细分（256256或1616）q粗格网、基本格网和细分格网都采用线性四叉树编码方法（Morton码），M0表示粗格网的地址码、M1表示基本格网的地址码、M2表示细分格网的地址码2 2）矢量栅格一体化结构）矢量栅格一体化结构q三个基本约定是：点状地物或结点，仅存储一个位置数据线状地物由一组填满路径的元子表达面状地物由由一组填满路径的元子表达边界线和内部区域面状地物的数据结构7.7.镶嵌数据结构镶嵌数据结构镶嵌数据结构包括：q规则镶嵌数据结构q不规则镶嵌数据结构q规则镶嵌数据结是用规则的小面块集合来逼近自然界不规则的地理单元q格网单元必须具有简单的形状和平移不变性，只有正方形和正六边形是规则的和可平移的q其中正方形具有无限可分分性，应用广泛1 1）规则镶嵌数据结）规则镶嵌数据结q正方形镶嵌数据结构可以构成格网系统，具体做法是用数学手段将一个 矩形格网叠置在所研究的 区域上，把连续的地理空间离散为互不覆盖的面块单元，以简化描述空间变化的机制，同时空间关系也比较明确q格网单元的 大小取决于区域研究精确度的需要和计算机系统的 处理能力，格网单元尺寸越小，分辨率越高，但数据量大q格网系统的优点数据结构表现为而二维矩阵结构，可以方便地沿水平方向和垂直方向遍历这种结构不需要进行坐标数字化，坐标隐藏在行列号中q 格网系统可以看成是栅格系统的一种特例，两者的 主要区别在于格网系统中，数据结构的逻辑记录是一个格网上的有关信息的集合栅格系统中存取单位只能是一个值当每个格网单元中只有一个属性值时，格网系统和栅格系统没有本质的区别栅格数据库一般呈矩阵状，而格网数据库可以呈不规则状q不规则镶嵌数据结是指用来进行镶嵌的小面块具有不规则的形状或边界q最典型和研究最多的不规则镶嵌是Voronoi图、Delaunay三角网 2 2）不规则镶嵌数据结）不规则镶嵌数据结qVoronoi图是俄国数学家M.G.Voronoi于1908年发现的几何构造，Voronoi多边形是不规则的最基本的和最重要的几何构造qDelaunay三角网是俄国数学家B.Delaunay于1934年发现的,Delaunay三角网是Voronoi图的对偶，将Voronoi图中各多边形单元的内点连接后得到一个布满整个区域而又互不重叠的三角网结构q设有平面点集S(P1,P2,Pn),其对应的Voronoi多边形V(P1),V(P2),V(Pn),其中V(Pi)是由距Pi最近的所有点组成的，也就是说，属于V(Pi)的每一个点x到Pi比到S的任何其它点Pj（ij）都近，即V(Pi)的内部是到Pi点比到S的其余点更近的全部点的轨迹qVoronoi图已成为GIS基础理论与算法中的一项重要内容，在空间邻近关系建立、空间区域划分、空间邻近查询、空间邻近分析和专题制图等方面有重要作用，可以有效地进行目标的邻近关系分析,在气象、地质、生态、城市规划等领域得到广泛应用qDelaunay三角网可以由Voronoi图中构造，也可以根据离散点直接构造，有关文献地理信息系统原理与算法一书中有专门的介绍，第五章将会介绍由离散点构造Delaunay三角网的方法qDelaunay三角网有多种存储方法，其中以三角形为核心的存储结构中，设立三个表三角形与相邻三角形三角形与三角形的三个顶点顶点坐标与高程8.8.四叉树数据结构四叉树数据结构四叉树分割的基本思想：首先把一幅图象或一幅栅格地图等分成四部分，如果检查到某个子区的所有格网都含有相同的值（灰度或属性值），那么，这个子区域就不再往下分割；否则，把这个区域再分割成四个子区域，这样递归地分割，直至每个子块都只含有相同的灰度或属性值为止常规四叉树及其分解过程常规四叉树方法除了记录叶结点外，还要记录中间结点，结点之间的联系靠指针表达，所以有时也叫指针四叉树常规四叉树方法靠指针来维护父子之间的相互关系，不仅增加存储量，而且增加了操作的复杂性常规四叉树在数据索引和图幅索引等方面得到应用，但在数据压缩和GIS数据结构领域人们更多采用线性四叉树q线性四叉树只存储最后叶结点的信息，即结点的位置、大小和格网值，叶结点的编号需要遵照一定的 规则，这种编号称为地址码，它隐含了叶结点的位置信息q叶结点位置采用基于四进制或十进制的Morton码表示（加拿大学者Morton于1966年提出）；叶结点的大小用结点的深度或层次表示1 1）线性四叉树线性四叉树q基于四进制的Morton码的生成和四叉树的建立有两种不同的方案一是用自上而下分裂的方式在建立四叉树的过程中逐步产生Morton码另一种是先计算每个格网的Morton码，然后按一定的扫描方式采用自下而上的合并方法建立四叉树先将二维矩阵元素的 下表转换成Morton码，并将元素按码的升序排列成线性表在排好的 线性表中，依次检查四个相邻的Morton码对应的 格网值，如果相同则合并为一大块，否则将这四个格网记盘（Morton码、深度、格网值）第一轮检测完后，依次检查每四个大块循环下去直到没有能够合并的 块为止第二种方法的效率高从底向上(down-top)的合并方法 从底向上(down-top)的合并方法中对 Morton码的扫描顺序 q上面介绍的基于四进制的Morton码以及建立四叉树的方法仍存在两方面的缺点一是码的外存开销大，由于大多数语言不支持四进制变量，需要用十进制长整形表示Morton码，显然是一种浪费二是运算效率不高qMark等人（1989）建议采用基于十进制的Morton码作为线性四叉树的地址码，并且采用自下而上的合并方法建立四叉树q与计算四进制的Morton码类似，计算MD时也是先将十进制的行号和列号转换为一种特殊码，称为伪码(If,Jf)，伪码采用如下公式计算：十进制Morton码与行列号之间的关系2 2）二维行程编码）二维行程编码q在生成的线性四叉树中，仍然存在前后叶结点的值相同的情况，因而可以采取进一步的压缩表达，即将格网值相同的前后结点合并成一个值，形成新的线性列表二维行程编码记录属性变化点记录不同大小块的属性q二维行程编码中前后两个地址码之差表达了该行程码的格网数，它可以直接表示该子块的大小q二维行程编码利用了线性四叉树的地址码，但不是结构规则的四叉树，甚至已经失去了四叉树的概念，然而它的好处是：压缩效率更高、节省存储空间，方便以后的插入、删除和修改等操作q对于三维立方体可以构成八叉树数据结构八叉树数据结构，细分格网和编码与四叉树一致先将格网所在I、J、K方向的 行号转换为二进制，然后按 K、I、J二进制交替组合，再转换成十进制，就可得到八叉树的十进制Morton码例如，I=3（0 1 1），J=0（0 0 0），K=3（0 1 1）交叉后为 0 0 0 1 1 0 1 1 0 =54X(I)Y(J)Z(K)I=3（0 1 1），J=2（0 1 0），K=0（0 0 0）0 0 0 0 1 1 0 1 0 26I=3（0 1 1），J=2（0 1 0），K=3（0 1 1）0 0 0 1 1 1 1 1 0 629.9.超图数据结构超图数据结构q法国巴黎大学Francois Bouille教授20世纪80年代初想欧洲航天研究发展局提交的超图数据结构（The Hypergraph Based Data Structure-HBDS）报告中提出的新的数据结构理论。该理论以超图和数据集合理论为基础，使原有数据结构理论面目一新，引起了国际上的广泛重视1 1）超图的概念）超图的概念q超图的概念是图的概念的一个扩展，在图集G（V,X）中，X的每一个元素可以看作是V的一个二元子集，在超图中，我们考虑任意的子集q设V=v1,v2,vp 是一个非空有限集，令 X=x1,x2,xq 是V的q个子集的一个组，则称二元组H（V,X）为一个超图，p称为超图H的“阶”，max|xi|称为H的“秩”，V的元素称为H的“顶点”，而X的元素称为H的“边”q一个超图可以用一个图解来表示，用平面上的一些几何点来代表H的顶点，若|xi|2，用一条封闭曲线把xi的元素围起来；若|xi|=2，则用一条曲线联结xi中的两个顶点；若|xi|=1，则用一条闭曲线联结xi中唯一的一个顶点和它自身q性能完备的空间数据结构应该能够对复合制图物体进行表示，其中包含与它们有关的空间的和非空间的 属性与联系，超图数据结构就是这样一种结构q超图数据结构是一种基于现象的数据结构，使用类别、物体、属性和关系这四种抽象数据类型，为表示基本地理实体、复合地理实体以及它们的空间和 非空间属性提供了有效手段 2 2）超图数据结构的基本概念）超图数据结构的基本概念q类别是同类物体的集合，如公路类q类别的属性即类别的性质，如公路的等级、路面材料q类别的元素叫做物体，类别中的一个个体，如一条特定的公路q物体的属性是类别属性的具体体现2 2）超图数据结构的基本元素）超图数据结构的基本元素q类别间的联系表明了在同一类别或不同类别物体之间可能的联系两个类别之间可以有多种联系，每一种联系是表示不同性质的联系，如公路与城镇物体之间的联系表示物体之间实际存在的 联系，如某条公路与不同的路段之间的联系联系可以是层次性的（公路与路段，组成），也可以是非层次性的（公路与城镇，连接）层次性的联系有两种，一种是类别间的层次联系，另一种是物体间的层次联系，如下图q类别间的层次联系：一个类别可有一个双亲类别，也可以有一个或多个子女类别（或空），是一种树结构q物体间的层次联系：它是类别间层次联系的具体体现q类别之间的或物体之间不仅有竖向联系，而且有横向联系或非层次联系q超图数据结构的主要优点：它能够区别信息的两种基本结构（层次的和非层次的），并表明任何一种复杂的信息结构都可以根据这两种信息结构来建立本章重点与作业本章重点与作业v重点重点q掌握空间实体、空间对象的概念；掌握矢量数据结构和栅格数据结构的定义、表示方法以及它们的 优缺点；四叉树数据结构以及指针四叉树、线性四叉树、二维行程四叉树的编码方法q了解地理现象的几何分类、空间对象的定义、空间对象关系、混合数据结构与一体化数据结构、镶嵌数据结构、超图数据结构v作业作业q1、空间实体和空间对象的定义，空间实体的描述内容q2、画图阐述有拓扑关系的矢量数据结构q3、什么是栅格数据结构，压缩栅格编码有几种方式？每种方式的优缺点？q4、简述什么是四叉数结构，采用十进制Morton码分别用线性四叉树和二维行程编码表示下图数据AABBAABBABBBAAAA