空间数据的表达方法.ppt

第三章第三章空间数据的表达方法空间数据的表达方法 客观的地理系统客观的地理系统自然环境系统自然环境系统社会经济环境系统社会经济环境系统如何把有关的空间数据组织到计算机系统中如何把有关的空间数据组织到计算机系统中?1）确定专题领域实际模型；）确定专题领域实际模型；2）建立表达实际模型的概念模型；）建立表达实际模型的概念模型；3）建立为实现概念模型的数据结构；）建立为实现概念模型的数据结构；4）确定数据文件在数据库中的组织方式。）确定数据文件在数据库中的组织方式。空间实际模型空间实际模型:指在研究区（项目所相关的空间区域）指在研究区（项目所相关的空间区域）内与某领域有关的实际存在的物质世界，它包含所有内与某领域有关的实际存在的物质世界，它包含所有能够被人们直接和不能直接观察到的各种有关信息。能够被人们直接和不能直接观察到的各种有关信息。空间数据模型空间数据模型:对有关真实世界的一种抽象表达，可对有关真实世界的一种抽象表达，可称为概念模型。称为概念模型。空间数据结构空间数据结构：把概念模型转变为计算机系统所能：把概念模型转变为计算机系统所能接受的数据结构和逻辑关系。接受的数据结构和逻辑关系。现实世界真实模型现实世界真实模型空间数据模型空间数据模型空间数据结构空间数据结构数据库：空间数据物数据库：空间数据物理结构理结构空间数据复原空间数据复原空间数据处理空间数据处理空间数据查询空间数据查询空间数据分析空间数据分析地理信息系统为什么要研究数据模型地理信息系统为什么要研究数据模型l3.1 空间信息空间信息l3.2 空间数据模型空间数据模型l3.3 空间数据结构空间数据结构l3.4 地貌的表达地貌的表达数字化地形模型数字化地形模型3.1空间信息空间信息1.空间性空间性空间位置：坐标数据空间位置：坐标数据 不同坐标之间可以转换不同坐标之间可以转换空间位置关系：拓扑关系空间位置关系：拓扑关系2.属性：属非空间数据属性：属非空间数据3.时间性：空间特征、属性特征独立地随时间变化时间性：空间特征、属性特征独立地随时间变化一、空间信息特点一、空间信息特点二、空间实体的属性信息分类二、空间实体的属性信息分类 二元型：二元型：等级型：等级型：数量型：数量型：非数量型：非数量型：有无有无；是、；是、否否地位级、火地位级、火险等级等险等级等坡向、坡位，坡向、坡位，植被等植被等面积、重量、面积、重量、长度等长度等三、空间实体的度量信息三、空间实体的度量信息（2）无约束的几何距离：）无约束的几何距离：（1）定位信息：点、线、面等用坐标对、）定位信息：点、线、面等用坐标对、坐标串、闭合坐标串描述。坐标串、闭合坐标串描述。D（P，P）=0D（P1，P2）0D（P1，P2）=D（P2，P1）D（P1，P2）=D（P1，P3）+D（P3，P2）距离特点：距离特点：（3）有约束条件的距离：有效距离）有约束条件的距离：有效距离周长：周长：面积：面积：四、空间实体的拓扑信息四、空间实体的拓扑信息l1、拓扑关系概念：是明确定义空间关系、拓扑关系概念：是明确定义空间关系的一种数学方法。在的一种数学方法。在GIS中，用来描述并中，用来描述并确定空间的点线面之间的关系及属性，确定空间的点线面之间的关系及属性，并可实现相关的查询和检索。并可实现相关的查询和检索。2、拓扑关系特点：、拓扑关系特点：1）独立于坐标系统的几何关系）独立于坐标系统的几何关系2）不随几何实体平移）不随几何实体平移 旋转旋转 缩放而变化缩放而变化拓扑关系反映了空间实体间的逻辑关系，拓扑关系反映了空间实体间的逻辑关系，不需要坐标、距离信息，不受比例尺限不需要坐标、距离信息，不受比例尺限制，也不随投影关系变化。制，也不随投影关系变化。理解拓扑变换和拓扑属性时，我们可以设想理解拓扑变换和拓扑属性时，我们可以设想一块高质量的橡皮，它的表面是欧几里德平一块高质量的橡皮，它的表面是欧几里德平面，可被任意拉伸压缩，但不能扭转折叠。面，可被任意拉伸压缩，但不能扭转折叠。表面上有由结点、弧、环和区域组成的图形。表面上有由结点、弧、环和区域组成的图形。若对该橡皮进行任意拉伸、压缩，但不扭转若对该橡皮进行任意拉伸、压缩，但不扭转和折叠，则在橡皮形状的这些变换中，图形和折叠，则在橡皮形状的这些变换中，图形的一些属性将得到保留，有些属性将消失。的一些属性将得到保留，有些属性将消失。拓扑和非拓扑属性拓扑和非拓扑属性两点之间的距离两点之间的距离一个点指向另一个点的方向一个点指向另一个点的方向弧段的长度弧段的长度一个区域的周长一个区域的周长一个区域的面积一个区域的面积一个点在一个弧段的端点一个点在一个弧段的端点一个弧段是一个简单的弧段一个弧段是一个简单的弧段一个点在一个区域的边界上一个点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部一个点在一个区域的外部一个点在一个区域的外部一个面是一个简单的面（无岛）一个面是一个简单的面（无岛）一个面的连通性一个面的连通性非拓扑属性非拓扑属性拓扑属性拓扑属性 拓扑变换拓扑变换（橡皮变换）（橡皮变换）3、空间对象的、空间对象的拓扑空间关系拓扑空间关系0 拓扑元素：拓扑元素：q 点：孤立点、线的端点、面的首尾点、链的连接点点：孤立点、线的端点、面的首尾点、链的连接点q 线：两结点之间的有序弧段，包括链、弧段和线段线：两结点之间的有序弧段，包括链、弧段和线段q 面：若干弧段组成的多边形面：若干弧段组成的多边形0 基本拓扑关系基本拓扑关系q 关联：不同拓扑元素之间的关系关联：不同拓扑元素之间的关系q 邻接：相同拓扑元素之间的关系邻接：相同拓扑元素之间的关系q 包含：面与其他元素之间的关系包含：面与其他元素之间的关系q 层次：相同拓扑元素之间的层次关系层次：相同拓扑元素之间的层次关系q 拓扑元素量之间的关系：欧拉公式拓扑元素量之间的关系：欧拉公式0 点、线、面之间的拓扑关系点、线、面之间的拓扑关系起点终点中间点弧段1弧段3弧段2弧段4点:面:弧:相邻相邻相交相交重叠重叠分离分离包含包含点点点点点点线线点点面面线线面面面面面面线线线线欧拉公式欧拉公式：欧拉公式在欧拉公式在GIS中有着重要的意义，中有着重要的意义，主要用来检查空间拓扑关系的正确主要用来检查空间拓扑关系的正确性，能发现点、线、面不匹配的情性，能发现点、线、面不匹配的情况和多余、遗漏的图形元素。况和多余、遗漏的图形元素。n=4，a=4b=1，c=1n=6，a=5b=2，c=1，p=2（图形数）n=4，a=5b=2，c=1n=10，a=12b=3，c=1c+a=n+bn:结点数结点数a:弧段数弧段数b:多边形数多边形数c:常数，为多边形地图特征。常数，为多边形地图特征。若若b包含边界里面和外面的多边形，则包含边界里面和外面的多边形，则c=2，若若b仅包含边界内部多边形，则仅包含边界内部多边形，则c=1主要拓扑关系主要拓扑关系拓扑的邻接性拓扑的邻接性结点之间结点之间a e cbda c deb-1011e1-100d01-10c101-1b1001-aedcba面块之间面块之间 cdab ad bc-111d1-10c11-1b101-adcba空间拓扑关系表达空间拓扑关系表达关系表关系表a ab bc cd de ef fg gA AC CB BD DE EP4P4P0P0P1P1P2P2P3P3面域与弧段的拓扑关系表面域与弧段的拓扑关系表 多边形多边形弧弧 段段 P P1 1a,b,c,-ga,b,c,-g P P2 2b,d,fb,d,f P P3 3c,f,ec,f,e P P4 4g g主要拓扑关系主要拓扑关系拓扑的关联性拓扑的关联性 弧段与结点的拓扑关系表弧段与结点的拓扑关系表 弧弧 段段结结 点点 a A,B a A,B b b B,DB,D c c D,A D,A d d B,CB,C e e C,AC,A f f C,D C,D g g E,E E,EabcdefgACBDEP4P0P1P2P3结点与弧段的拓扑关系表结点与弧段的拓扑关系表结点与弧段的拓扑关系表结点与弧段的拓扑关系表 结结结结 点点点点弧弧弧弧 段段段段 A A A A a,c,e a,c,e a,c,e a,c,e B B B B a,d,b a,d,b a,d,b a,d,b C d,e,f C d,e,f C d,e,f C d,e,f D b,f,c D b,f,c D b,f,c D b,f,c E E E E g g g g abcdefgACBDEP4P0P1P2P3 弧段与多边形拓扑关系表弧段与多边形拓扑关系表弧段弧段 左多边形左多边形 右多边形右多边形 a a P P0 0 P P1 1 b b P P2 2 P P1 1 c P c P3 3 P P1 1 d d P P0 0 P P2 2 e e P P0 0 P P3 3 f f P P3 3 P P2 2 g g P P1 1 P4 P4a ab bc cd de ef fg gA AC CB BD DE EP4P4P0P0P1P1P2P2P3P3多边形与多边形拓扑关系表多边形与多边形拓扑关系表 P1 P2 P3 P4 P1 P2 P3 P4 P1 P1 -1 1 1 1 1 1 P2 P2 1 -1 -1 0 1 0 P3 1 1 -0 P3 1 1 -0 P4 P4 1 0 0 1 0 0-a ab bc cd de ef fg gA AC CB BD DE EP4P4P0P0P1P1P2P2P3P3拓扑的邻接性拓扑的邻接性P1P2P1P2P3P3P1P2P3P3简单包含简单包含多层包含多层包含等价包含等价包含拓扑的包含性拓扑的包含性3.1.4空间实体的网络信息空间实体的网络信息 指很多线状实体空间的网络模指很多线状实体空间的网络模型，如道路、河流、航空护林型，如道路、河流、航空护林的航线网、通讯网、防火阻隔的航线网、通讯网、防火阻隔带网等。带网等。3.2空间数据模型空间数据模型确定空间数据模型的基本原则：确定空间数据模型的基本原则：1、把所基本空间信息储存于计算机介质中、把所基本空间信息储存于计算机介质中2、便于对数据库信息的复原、查询、分析和、便于对数据库信息的复原、查询、分析和处理等的高效与可能性处理等的高效与可能性 一一.规则格网式空间数据模型：规则格网式空间数据模型：栅格数据模型栅格数据模型 空间单元人为划定成空间单元人为划定成大小相等的正方形网大小相等的正方形网格，有着统一的定位格，有着统一的定位参照系。每个空间参照系。每个空间 单元只记录其属性值，单元只记录其属性值，而不记录它的坐标值。而不记录它的坐标值。222222221777 7777222222221777 7777222222221777 7777222222217777 7777222222117777 7777222221177777 7777222214417777 7777111144441777 7777444444444177 7777444444444417 7777444444444441 7777444444444444 1777444444444444 4177444444444444 4417444444444444 4441444444444444 4444点点线线面面 对于栅格数据结构对于栅格数据结构点：为一个像元点：为一个像元线：在一定方向上线：在一定方向上连接成串的相邻像连接成串的相邻像元集合。元集合。面：聚集在一起的面：聚集在一起的相邻像元集合。相邻像元集合。栅格数据：栅格数据：坐标系与描述参数坐标系与描述参数YY：列：列：列：列XX：行：行：行：行西南角格网坐标西南角格网坐标西南角格网坐标西南角格网坐标（XXWSWS，YYWSWS）格网分辨率格网分辨率格网分辨率格网分辨率（一）特点（一）特点:1.用离散的量化栅格值表示空间实体用离散的量化栅格值表示空间实体2.描述区域位置明确，属性明显描述区域位置明确，属性明显3.数据结构简单，易与遥感结合数据结构简单，易与遥感结合4.难以建立地物间拓扑关系难以建立地物间拓扑关系5.图形质量低，数据量大图形质量低，数据量大（二）栅格数据的取值二）栅格数据的取值A BC D每个栅格元素只能取一每个栅格元素只能取一个值，实际上一个栅格个值，实际上一个栅格可能对应于实体中几种可能对应于实体中几种不同属性值，存在栅格不同属性值，存在栅格数据取值问题数据取值问题1、面积占优法、面积占优法栅格中占最大面积的属性值为它的属性栅格中占最大面积的属性值为它的属性A BC DBDDDBBDCBBCCBBAA2、长度占优法、长度占优法将网格中心画一横线，用横线所占最长部将网格中心画一横线，用横线所占最长部分属性值作为栅格属性分属性值作为栅格属性A BC DBDDDBBDCBBCCBBAA3、中心点法、中心点法将栅格中心点的值作为栅格元素值将栅格中心点的值作为栅格元素值A BC DBDDDBBDCBBCCBBAA4、重要性法、重要性法某些主要属性，只要在栅格中出现就把该属某些主要属性，只要在栅格中出现就把该属性作为栅格属性性作为栅格属性A BC DDDDDBDDCBBAABBAA（三）栅格数据的获取（三）栅格数据的获取1、目读法：适用于所选区域范围小，栅格、目读法：适用于所选区域范围小，栅格单元尺寸大的情况。单元尺寸大的情况。2、从扫描仪获取：高精度，快速度，数据、从扫描仪获取：高精度，快速度，数据格式标准化。格式标准化。3、从摄像机获取：栅格元素数固定、从摄像机获取：栅格元素数固定 512512 102410244、从遥感中获取：周期性，动态性，可自、从遥感中获取：周期性，动态性，可自动提取专题信息。动提取专题信息。5、从矢量数据转换成栅格数据、从矢量数据转换成栅格数据二二.面向实体的空间数据模型：面向实体的空间数据模型：矢量数据模型矢量数据模型 l把连续的空间按实体集中，每个实体把连续的空间按实体集中，每个实体分割成空间单元，记录描述它们位置的分割成空间单元，记录描述它们位置的坐标数据。坐标数据。l必须有一个参照坐标系和划分地理实必须有一个参照坐标系和划分地理实体的分类系统，坐标系决定矢量数据模体的分类系统，坐标系决定矢量数据模型的精度。型的精度。空间实体的矢量数据表达空间实体的矢量数据表达（一）特点：（一）特点：1.用离散的用离散的点或线点或线描述地理现象及特征描述地理现象及特征2.用拓扑关系描述矢量数据之间关系用拓扑关系描述矢量数据之间关系3.面向目标的操作面向目标的操作4.数据结构复杂且难以同遥感数据结合数据结构复杂且难以同遥感数据结合5.难于处理位置关系难于处理位置关系空间对象（实体）的地图表达空间对象（实体）的地图表达空间对象（实体）的地图表达空间对象（实体）的地图表达点：位置：（点：位置：（x，y）属性：符号属性：符号线：位置：线：位置：（x1,y1),(x2,y2),(xn,yn)属性：符号属性：符号形状、颜色、尺寸形状、颜色、尺寸面：面：位置：位置：(x1,y1),(x2,y2),(xi,yi),(x1,y1)属性：符号变化属性：符号变化 （二）矢量数据的获取（二）矢量数据的获取外业测量获取（如外业测量获取（如GPS）用跟踪数字化方法获取数据用跟踪数字化方法获取数据从栅格数据转换成矢量数据从栅格数据转换成矢量数据地图的矢量和栅格表示地图的矢量和栅格表示(x(x1 1,y,y1 1)(x(x2 2,y,y2 2)(x(x3 3,y,y3 3)(x(x4 4,y,y4 4)0 00 00 00 00 00 01 10 00 00 00 00 03 33 30 00 08 81 10 04 44 44 40 00 03 33 33 30 00 01 14 44 44 44 44 40 03 33 33 30 01 10 04 44 44 44 44 44 43 33 33 30 01 10 04 44 44 44 44 40 00 00 00 01 17 70 00 04 44 44 40 00 00 00 00 01 15 50 00 00 00 00 00 07 70 01 15 55 55 55 50 00 00 00 00 00 00 01 15 55 55 55 50 00 00 08 80 00 01 10 05 55 50 00 00 00 00 00 00 05 5地图的矢量和栅格表示地图的矢量和栅格表示3.3空间数据结构空间数据结构空间数据结构空间数据结构：把概念模型转变为计算机系统所能：把概念模型转变为计算机系统所能接受的数据结构和逻辑关系。接受的数据结构和逻辑关系。图形数据图形数据属性数据属性数据编码编码(数据结构数据结构)空间空间实体实体数据存入数据存入计算机计算机一、基于规则格网空间数据模型的数据一、基于规则格网空间数据模型的数据 结构结构(栅格数据结构栅格数据结构)（一）二维矩阵数据结（一）二维矩阵数据结构构 l 把规则格网平面作为把规则格网平面作为一个二维矩阵进行数学一个二维矩阵进行数学表达，每个栅格是具有表达，每个栅格是具有行、列位置的矩阵元素，行、列位置的矩阵元素，该空间实体属性编码值该空间实体属性编码值赋予矩阵元素。赋予矩阵元素。2221177722221777222222222227777744447777优点：优点：1易于实现用循环语句编程，实现快速运算易于实现用循环语句编程，实现快速运算2易于实现空间属性的分解与分类，易于实现易于实现空间属性的分解与分类，易于实现空间分析中叠加等操作空间分析中叠加等操作缺点：缺点：数据存储量大数据存储量大基本要素包括：行，列，属性值（基本要素包括：行，列，属性值（N，M，Xij）其中行、列值隐性，属性值显性。其中行、列值隐性，属性值显性。（二）费尔曼链码（二）费尔曼链码（边界编码）（边界编码）曲线或边界中有一点（曲线或边界中有一点（i,j）其相邻栅格）其相邻栅格在在8个邻域方向上个邻域方向上NW（5）N（6）NE（7）W（4）（i,j）E(0)SW(3)S(2)SE(1)方向方向E SE S SW W NW N NE 编号编号0 1 2 3 4 5 6 7i增量增量0 1 1 1 0 -1 -1 -1j增量增量1 1 0 -1 -1 -1 0 10ij42200654026SE(1)S(2)SW(3)E(0)（i,j）W（4）NE（7）N（6）NW（5）0123456789101 2 3 4 5 6 7 8 9 1077000222227701333355554450#1#2标标号号高高程程起止起止行列行列链链 码码#1100m3，00，7，7，0，0，0，0，2，0，1，2，2，2，2，4，3，3，4，4，4，5，5，6，5，6，6#2200m4，20，7，7，0，0，1，2，2，4，4，3，4，5优缺点：优缺点：数据压缩率强，便于计算长度，面积，数据压缩率强，便于计算长度，面积，便于表示图形凹凸部分，易于储存。便于表示图形凹凸部分，易于储存。但难于实现叠置运算，不便于合并插入操但难于实现叠置运算，不便于合并插入操作。作。适于对曲线和边界进行编码适于对曲线和边界进行编码（三）游程（行程）编码（三）游程（行程）编码 游程游程：以行为单位，将栅格数据矩阵中属性：以行为单位，将栅格数据矩阵中属性相同的连续栅格视为一游程。相同的连续栅格视为一游程。2228800058888770第一行：第一行：4个游程个游程第二行：第二行：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)游程长度编码：游程长度编码：优点：优点：数据压缩率高，易于实现叠置，检索数据压缩率高，易于实现叠置，检索运算。运算。缺点：缺点：只考虑水平分解元素之间相关性而未考只考虑水平分解元素之间相关性而未考虑垂直分解元素之间相关性，又称一维虑垂直分解元素之间相关性，又称一维游程编码。游程编码。（四）块状编码（四）块状编码 以正方形区域为单元对块状地物的栅格以正方形区域为单元对块状地物的栅格数据进行编码，实质是把栅格阵列中同一属数据进行编码，实质是把栅格阵列中同一属性方形区域各元素映射成一个元素系列。性方形区域各元素映射成一个元素系列。编码方式：（行号，列号，半径，代码）编码方式：（行号，列号，半径，代码）0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（），（1 1，5 5，1 1，5 5），），（1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1，3 3），），（5 5，4 4，2 2，3 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。（四）块状编码（四）块状编码特点：特点：1、面状地物所能包含的正文形越大，多边、面状地物所能包含的正文形越大，多边形边界越简单，块码编码效率超高；形边界越简单，块码编码效率超高；2、图形比较碎，多边形边界复杂的图形，、图形比较碎，多边形边界复杂的图形，数据压缩率低；数据压缩率低；3、利于计算面积、合并插入等操作。、利于计算面积、合并插入等操作。（五）四叉树编码（五）四叉树编码（QuadtreeCode）1、常规四叉树、常规四叉树基本思想：把一幅图像或一幅栅格地图基本思想：把一幅图像或一幅栅格地图等分成等分成4部分，逐块检查其栅格值，若部分，逐块检查其栅格值，若每个子区都含有相同值，则该子区不再每个子区都含有相同值，则该子区不再往下分割，否则将该区域再分割往下分割，否则将该区域再分割4个子个子区域，如此递归分割直到每个子块都含区域，如此递归分割直到每个子块都含有相同的灰度或属性为止。有相同的灰度或属性为止。2 23 3 2 23 30 01 12 23 31011101112131213 NW 0 NE 1 SW 2 SE 3A122对一幅对一幅2N 2N的栅格阵列，最大深度为的栅格阵列，最大深度为N，可能有的层次为可能有的层次为0，1，2，N，那么，那么，每层的栅格宽度为：每层的栅格宽度为：2（最大深度（最大深度-当前层次）当前层次）反映了所在叶结点表示的正文形集合的大反映了所在叶结点表示的正文形集合的大小。小。缺点：缺点：所占空间比较大，不仅要记录每个结点，所占空间比较大，不仅要记录每个结点，还要记录一个前趋结点和四个后继点，还要记录一个前趋结点和四个后继点，以及反映结点之间联系，对栅格数据进以及反映结点之间联系，对栅格数据进行运算时，还要作遍历树结点的运算，行运算时，还要作遍历树结点的运算，增加操作复杂性。增加操作复杂性。产生线性四叉树。产生线性四叉树。2.线性四叉树线性四叉树以四叉树的方式组织数据，但不以四叉树方以四叉树的方式组织数据，但不以四叉树方式存储数据。式存储数据。通过编码四叉树的叶结点表示数据的层次和通过编码四叉树的叶结点表示数据的层次和空间关系。叶结点具有一个反映位置的关键空间关系。叶结点具有一个反映位置的关键字，亦称位置码。实质是把原来大小相等等字，亦称位置码。实质是把原来大小相等等栅格集合转换成大小不等的正方形集合，对栅格集合转换成大小不等的正方形集合，对不同尺寸和位置的正方形集合赋予一个位置不同尺寸和位置的正方形集合赋予一个位置码。码。(19)0(18)0(12)0(11)0(16)(15)(17)0(14)(13)(10)1（9）1(7)(6)(5)(4)（3）1（8）0（2）0（1）0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 01 1 0 0 0 0 0 01 1 1 1 0 0 0 0 1 1 1 1 1 0 0 01 1 1 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 03.线性四叉树编码线性四叉树编码（1）基于深度和层次码的线性四叉树编码）基于深度和层次码的线性四叉树编码 它通过记录叶结点的深度码和层次码来描述它通过记录叶结点的深度码和层次码来描述叶结点的位置，叶结点的位置，2N为层次码。为层次码。如图中叶结点（如图中叶结点（7）的编码为：）的编码为：层次码层次码深度码深度码第一层第一层 第二层第二层第三层第三层0 01 1 1 10 0 1 1此位置码十进制值此位置码十进制值=2438 9 80 0 1 01 1 1 0 0 0 189 6 20 0 1 01 1 1 1 0 0 198 3 40 0 1 01 1 0 1 0 0 178 1 90 0 1 11 1 0 0 1 1 168 0 3 0 0 1 11 1 0 0 1 0 157 8 70 0 1 11 1 0 0 0 1 147 7 1 0 0 1 11 1 0 0 0 0 137 0 6 0 0 1 01 0 1 1 0 0 126 4 20 0 1 01 0 1 0 0 0 115 7 80 0 1 01 0 0 1 0 0 105 1 4 0 0 1 01 0 0 0 0 0 92 5 7 0 0 0 11 0 0 0 0 0 82 4 3 0 0 1 10 0 1 1 1 1 72 2 70 0 1 10 0 1 1 1 0 62 1 10 0 1 10 0 1 1 0 1 51 9 50 0 1 10 0 1 1 0 0 41 3 00 0 1 00 0 1 0 0 0 36 60 0 1 00 0 0 1 0 0 220 0 1 00 0 0 0 0 0 1十进制码十进制码二进制码二进制码叶结点号叶结点号（2）基于四进制的线性四叉树）基于四进制的线性四叉树编码编码对每个栅格进行编码得表对每个栅格进行编码得表a。检查相邻。检查相邻4个码的属个码的属性值，如相同进行合并，除去最低值。经过一次检性值，如相同进行合并，除去最低值。经过一次检测后，再检测上层相邻四个块码编的属性值，如相测后，再检测上层相邻四个块码编的属性值，如相同再合并。循环到没有能合并的子块为止，得表同再合并。循环到没有能合并的子块为止，得表b。首先将栅格阵列的行列值分别转换成二进制码，得首先将栅格阵列的行列值分别转换成二进制码，得二进制行号二进制行号Iy b,列号列号 J y b，然后求出四进制四叉树，然后求出四进制四叉树码码m=2*Iy b +J y b表表a333332323322233232223222111331330321320231230221220110313312303302213212203202101311310301300211210201200100133132123122033032023022011131130121120031030021020010113112103102013012003002001111110101100011010001000000111110101100011010001000333223223033023130130021200330320310300210100表表b000000100属性值属性值1101100100属性值属性值21201033032031030020100四进制码四进制码191817161514131211叶结叶结点号点号103393283173036302530143003232221四进制码四进制码叶结叶结点号点号四进制的线性四叉树编码四进制的线性四叉树编码四进制线性四叉树编码的特点四进制线性四叉树编码的特点：优点是便于实现行列值及其编码之间的优点是便于实现行列值及其编码之间的转换；转换；缺点是存储开销大，且一般软件都不支缺点是存储开销大，且一般软件都不支持四进制。持四进制。(3)基于十进制的线性四叉树编码基于十进制的线性四叉树编码编码：编码：将二进制的行列号按位交错排列，可得将二进制的行列号按位交错排列，可得到四叉树叶结点的二进制地址码，进而到四叉树叶结点的二进制地址码，进而将二进制码转成十进制码，得到四叉树将二进制码转成十进制码，得到四叉树编码。编码。0 0 1 1 1 0行号行号=011010=列号列号MD=14表表a经自下而上归并得表经自下而上归并得表b。依次检查表。依次检查表a中四个相邻叶结点的属性代码是否相同。中四个相邻叶结点的属性代码是否相同。若相同则归并成一个父结点，记下地址及若相同则归并成一个父结点，记下地址及代码。否则不予归并。然后再归并更高一代码。否则不予归并。然后再归并更高一层父结点，如此循环，直到不能归并为止。层父结点，如此循环，直到不能归并为止。636259584746434211161605756454441401105554515039383534101535249483736333210031302726151411100112928252413129801023221918763200121201716541000011111010110001101000100060564440515052494836321514131281640表表a表表b060056052051050049148044040136132016115114013012180400属性值属性值MD码值码值属性值属性值MD码值码值0491480401320161140121800四叉树游程编码四叉树游程编码特点：特点：比四进制节省储存空间，且前后两个比四进制节省储存空间，且前后两个MD码码之间差代表了叶结点的大小，还可进一步利用游之间差代表了叶结点的大小，还可进一步利用游程编码对数据进行压缩。程编码对数据进行压缩。优点：具有可变分辨率，能精确表示图形的细节优点：具有可变分辨率，能精确表示图形的细节部分，编码效率高；具有区域性质，适合于图形部分，编码效率高；具有区域性质，适合于图形图像的分析运算；便于岛的分析。图像的分析运算；便于岛的分析。（六）三维空间信息的数据结构（六）三维空间信息的数据结构 线性八叉树数据结构：从四叉树数据结构发展线性八叉树数据结构：从四叉树数据结构发展而来。原理是将空间区域不断分解成而来。原理是将空间区域不断分解成8个同样个同样大小立方体，直到同一区域的属性相同为止。大小立方体，直到同一区域的属性相同为止。或者将空间区域先按一定分辨率划分成三维的或者将空间区域先按一定分辨率划分成三维的栅格，然后按顺序每次比较栅格，然后按顺序每次比较8个相邻栅格区域，个相邻栅格区域，若属性相同则合并，依次递归，直到若属性相同则合并，依次递归，直到8个子区个子区域为单值为止。域为单值为止。0 10 12 32 37 74 54 5二二.基于地理实体的向量数据结构基于地理实体的向量数据结构面实体地图描述和定义：面实体地图描述和定义：（1）从图论空间来看，一个地图）从图论空间来看，一个地图G=（a,p）被看成是由顶点集（）被看成是由顶点集（p）被边集）被边集(a)所所连接的网，可称为多边形网；连接的网，可称为多边形网；（2）每个面实体（称为多边形）是由一）每个面实体（称为多边形）是由一组点子集或线子集所定义；组点子集或线子集所定义；（3）每个多边形是在一定的约束条件下）每个多边形是在一定的约束条件下某些线实体所构成的回路；某些线实体所构成的回路；（4）线与线实体呈链接关系而无交叉关系；）线与线实体呈链接关系而无交叉关系；（5）面实体之间有邻接和叠合包含关系；）面实体之间有邻接和叠合包含关系；（6）叠合包含关系可分半岛式及岛屿式；）叠合包含关系可分半岛式及岛屿式；（7）邻接多边形之间至少必有一个公共边）邻接多边形之间至少必有一个公共边（弧）；（弧）；（8）一条弧是由若干个点所组成，首、尾端）一条弧是由若干个点所组成，首、尾端点称为首结点和尾结点；点称为首结点和尾结点；（9）在一般情况下，一个结点至少连接三个）在一般情况下，一个结点至少连接三个以上的弧；以上的弧；（10）岛屿多边形与半岛多边形首尾结点重合，）岛屿多边形与半岛多边形首尾结点重合，它们本身只有一条弧，但连接半岛多边形的结它们本身只有一条弧，但连接半岛多边形的结点除了引出半岛多边形的弧之外，还至少引出点除了引出半岛多边形的弧之外，还至少引出另外两条以上的弧；另外两条以上的弧；（11）一幅地图上的多边形类型除了一般多边）一幅地图上的多边形类型除了一般多边形、岛屿多边形、半岛多边形之外，还必有一形、岛屿多边形、半岛多边形之外，还必有一个图幅边界多边形；个图幅边界多边形；（12）在由一般多边形和边界多边形）在由一般多边形和边界多边形构成的地图情况下（假设没有岛屿多构成的地图情况下（假设没有岛屿多边形及半岛多边形）在该幅地图上多边形及半岛多边形）在该幅地图上多边形、结点与弧的关系可由下式所定边形、结点与弧的关系可由下式所定义：义：Npl=NA+2-ND其中，其中，Npl多边形的个数多边形的个数NA弧数弧数ND结点数结点数A5A1A2A3A4A6A7A8A9A10A11P1P2P3P4P5P6P7124567abdcefg12如右图由如右图由1，2两个多变性组成两个多变性组成1多边形包括多边形包括a,b,c,d四条弧合并四条弧合并成一个闭合曲线，分别存储该曲成一个闭合曲线，分别存储该曲线上的点线上的点2多边形包括多边形包括c,e,f,g四条弧合并四条弧合并成一个闭合曲线，分别存储该曲成一个闭合曲线，分别存储该曲线上的点线上的点（一）面实体的非拓扑结构简单表达方法（一）面实体的非拓扑结构简单表达方法及相应的数据结构及相应的数据结构1.面实体简单的矢量表达方法面实体简单的矢量表达方法 逐一对每个多边形进行表达，把每个多边形表达成逐一对每个多边形进行表达，把每个多边形表达成一组边（弧）上的一组边（弧）上的X与与Y坐标。坐标。优点：优点：数据结构最简单，一个多边形是一个闭合的曲线，数据结构最简单，一个多边形是一个闭合的曲线，不被分解成弧段，也用不着考虑岛屿和半岛多边形不被分解成弧段，也用不着考虑岛屿和半岛多边形的问题的问题缺点缺点：1）相邻两多边形之间的界线数字化和储存两次，公）相邻两多边形之间的界线数字化和储存两次，公共边界两次数字化的数据不可能完全相同，会出现共边界两次数字化的数据不可能完全相同，会出现一些空隙一些空隙2）该方法不能产