2空间数据结构-2.ppt

《2空间数据结构-2.ppt》由会员分享，可在线阅读，更多相关《2空间数据结构-2.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、地理信息系统原理GIS第二章第二章 空间数据结构空间数据结构2-1空间实体及其描述空间实体及其描述 2-2栅格数据结构栅格数据结构2-3矢量数据矢量数据结结构构 2-5矢栅一体化数矢栅一体化数据结构据结构 二、二、地理实体的描述地理实体的描述四、四、实体间空间关系实体间空间关系一、一、地理实体地理实体三、三、实体的空间特征实体的空间特征一、图形表示一、图形表示 二、数据组织二、数据组织四、栅格四、栅格数据数据编码编码 三、栅格结构的建立三、栅格结构的建立2-6三维数据结构三维数据结构 2-4栅矢数据的比栅矢数据的比较较一、栅矢数据的比较一、栅矢数据的比较二、栅矢数据的选择二、栅矢数据的选择 一

2、、矢栅一体化概念一、矢栅一体化概念 三、一体化三、一体化结结构构设计设计 二、二、三个三个约约定和定和细细分分格网法格网法 二、八叉树结构二、八叉树结构一、概述一、概述三、四面体格网三、四面体格网五、参数函数表示法五、参数函数表示法四、三维边界表示法四、三维边界表示法一、图形表示一、图形表示 二、获取方式二、获取方式三、组织三、组织 四、编码方式四、编码方式 地理信息系统原理GIS2-3 2-3 矢量矢量数据数据结结构构 第二章第二章 GIS GIS 数据结构数据结构一、图形表示一、图形表示地理信息系统原理GIS二、矢量数据的获取方式二、矢量数据的获取方式2-3 2-3 矢量数据结构矢量数据结

3、构第二章第二章 GIS GIS 数据结构数据结构1)由外业测量获得由外业测量获得可利用测量仪器自动记录测量成果，然后转到地理数据库中。可利用测量仪器自动记录测量成果，然后转到地理数据库中。2)由栅格数据转换获得由栅格数据转换获得利用栅格数据矢量化技术，把栅格数据转换为矢量数据。利用栅格数据矢量化技术，把栅格数据转换为矢量数据。3)跟踪数字化跟踪数字化用跟踪数字化的方法，把地图变成离散的矢量数据。用跟踪数字化的方法，把地图变成离散的矢量数据。地理信息系统原理GIS三、矢量数据组织三、矢量数据组织 2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构点：坐标对（点

4、：坐标对（x,y）线线：坐坐标标对对系系列列(x1,y1).(xn,yn)面：首尾相同的坐标串面：首尾相同的坐标串关系表关系表几何位置坐标文件几何位置坐标文件连连接接矢量数据表示时矢量数据表示时应考虑以下问题应考虑以下问题：矢量数据自身的存贮和处理。矢量数据自身的存贮和处理。与属性数据的联系。与属性数据的联系。矢量数据之间的空间关系矢量数据之间的空间关系(拓扑关系拓扑关系)。+识别符识别符及及有关属性、其它属性有关属性、其它属性地理信息系统原理GIS点实体：点实体：2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构识别符识别符类型、序号类型、序号线实体线实体

5、其它属性其它属性:如三角点设立年代、材料等如三角点设立年代、材料等简单点要素简单点要素：记录符号、：记录符号、比例尺、方向比例尺、方向坐标属性坐标属性注记点注记点：记录有关字符的大小、方向、字体、排列等：记录有关字符的大小、方向、字体、排列等结点结点：记录符号、指针、与线相交的角度：记录符号、指针、与线相交的角度唯一标识码唯一标识码线标识码线标识码起始点起始点终止点终止点坐标对序列坐标对序列显示信息显示信息非几何属性非几何属性地理信息系统原理GIS四、矢量数据四、矢量数据编码方法编码方法2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构一、实体式（面条模型）

6、一、实体式（面条模型）二、索引式（树状）二、索引式（树状）三、双重独立地图编码三、双重独立地图编码四、链状双重独立地图编码四、链状双重独立地图编码地理信息系统原理GIS（一）实体式（一）实体式面条模型（面条模型（spaghetti）:以实体为单位记录其坐标以实体为单位记录其坐标2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构123456789101112131415P PP PP P实体实体坐标串坐标串P1x5,y5;x7,y7;x8,y8;x9,y9;x10,y10;x2,y2,x4,y4;x5,y5P2x5,y5;x7,y7;x8,y8;x9,y9;x

7、10,y10;x2,y2,x6,y6;x5,y5P3x15,y15;x11,y11;x12,y12;x13,y13;x14,y14,x15,y15Ax5,y5;x7,y7;x8,y8;x9,y9;x10,y10;x2,y2地理信息系统原理GIS3、岛岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。结构简单、直观、易实现以实体为单位的运算和显示。结构简单、直观、易实现以实体为单位的运算和显示。缺点缺点:1、相邻多边形的公共边界被数字化并存储两次，造成相邻多边形的公共边界被数字化并存储两次，造成数据冗余和碎屑多数据冗余和碎屑多边

8、形边形，造成数据不一致，浪费空间，导致双重边界不能精确匹配。，造成数据不一致，浪费空间，导致双重边界不能精确匹配。2、自成体系，自成体系，缺少多边形的邻接信息，无拓扑关系缺少多边形的邻接信息，无拓扑关系，难以进行邻域处理，难以进行邻域处理，如消除多边形公共边界，合并多边形。如消除多边形公共边界，合并多边形。适宜在简单的制图系统中，显示图形。适宜在简单的制图系统中，显示图形。2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构实体式编码的特点实体式编码的特点优点优点：地理信息系统原理GIS（二）树状索引式（二）树状索引式2-3 2-3 矢量数据结构矢量数据结构第

9、二章第二章 GIS GIS 数据结构数据结构对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。123456789101112131415P PP PP P1、点文件：、点文件：点号点号坐标坐标1x1,y1索引文件：索引文件：面号面号弧段号弧段号P1A,B,C3、面文件：、面文件：2、弧段文件、弧段文件:弧段号弧段号起点起点终点终点点号点号A527,8,9,10与实体式相比与实体式相比：优点：优点：用建索引的方法消除多边形数据的冗余和不一致，邻接信息、岛信息可在用建索引的方法消除多边形数据的冗余和不一致

10、，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查询。多边形文件中通过是否公共弧段号的方式查询。缺点缺点：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑：表达拓扑关系较繁琐，给相邻运算、消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工作量大，易出错。关系等带来困难，以人工方式建立编码表，工作量大，易出错。地理信息系统原理GIS（三）双重独立式编码（三）双重独立式编码简简称称DIME(DualIndependentMapEncoding)，是是美美国国人人口口统统计计系系统统采采用用的的一一种种编编码码方方式，是一种式，是一种拓扑拓扑编码结构。

11、编码结构。2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构1、点文件、点文件点号点号坐标坐标1x1,y12、线文件、线文件:线文件是以线文件是以线段线段为记录单位为记录单位 线号线号左多边形左多边形右多边形右多边形起点起点终点终点L210P1P2210123456789101112131415P PP PP P3、面文件、面文件面号面号线号线号P1L210,L109L43,L32关联关联邻接邻接关联关联连通连通拓扑关系明确拓扑关系明确地理信息系统原理GIS（四）（四）链状双重独立式编码链状双重独立式编码-拓扑数据结构拓扑数据结构 2-3 2-3 矢量数据结

12、构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构1、弧段坐标文件、弧段坐标文件：弧段号弧段号坐标系列（串坐标系列（串)Ax2,y2,X10,y102、弧段文件：链弧段文件：链面，链面，链结点关系结点关系 弧段号弧段号左多边形左多边形右多边形右多边形起点起点终点终点AP1P225123456789101112131415P PP PP P3、面文件、面文件面号面号弧段号弧段号P1A,B,-C4 4、点拓扑文件、点拓扑文件：结点结点链关系链关系 点号点号弧段号弧段号2A,B,D在拓扑结构中，多边形（面）在拓扑结构中，多边形（面）的边界被分割成一系列的线的边界被分割成一系列的线（弧、链、

13、边）和点（结点）（弧、链、边）和点（结点）等拓扑要素，点、线、面之间等拓扑要素，点、线、面之间的拓扑关系在属性表中定义，的拓扑关系在属性表中定义，多边形边界不重复。多边形边界不重复。将以将以线段线段为记录单位改为以为记录单位改为以弧段弧段为单位为单位链状双重独立式编码链状双重独立式编码地理信息系统原理GIS链状双重独立式编码链状双重独立式编码 特点特点1、拓扑关系明确、拓扑关系明确2、能表达岛信息、能表达岛信息3、以弧段为记录单位，满足实际应用需要。因为一般、以弧段为记录单位，满足实际应用需要。因为一般数字化一条街道时，必然有许多中间点，但我们在做空数字化一条街道时，必然有许多中间点，但我们在

14、做空间分析是却没有必要以这些中间点所组成的折线为研究间分析是却没有必要以这些中间点所组成的折线为研究对象，而应以整条弧段（某条街道）为研究对象对象，而应以整条弧段（某条街道）为研究对象.2-3 2-3 矢量数据结构矢量数据结构第二章第二章 GIS GIS 数据结构数据结构地理信息系统原理GIS一、矢量数据结构与栅格数据结构特征比较一、矢量数据结构与栅格数据结构特征比较2-4 2-4 栅格栅格-矢量数据的比较矢量数据的比较第二章第二章 GIS GIS 数据结构数据结构栅格栅格矢量矢量表达实体表达实体点、线、面点、线、面表达单元表达单元栅格单元实体表达方式表达方式编码方法直接编码（无压缩）实体式（

15、拓扑结构简单）行程编码索引式块式编码DIME编码链式编码链状DIME编码（完整拓扑结构）四叉树编码地理信息系统原理GIS二、矢量数据结构与栅格数据结构比较二、矢量数据结构与栅格数据结构比较2-4 2-4 栅矢数据的比较栅矢数据的比较第二章第二章 GIS GIS 数据结构数据结构 优点优点缺点缺点矢矢量量1、结结构构紧紧凑凑，冗冗余余度度低低，便便于于描描述述线或边界。线或边界。2、空间位置精度高、空间位置精度高3、利利于于网网络络、检检索索分分析析，提提供供有有效效的的拓拓扑扑编编码码，对对需需要要拓拓扑扑信信息息的的操操作作更更有效。有效。4、图形显示质量好，精度高。图形显示质量好，精度高。

16、1、数数据据结结构构复复杂杂，各各自自定定义义，不不便便于数据标准化和规范化，数据交换困难。于数据标准化和规范化，数据交换困难。2、多多边边形形叠叠置置分分析析困困难难，没没有有栅栅格格有效，表达空间变化性能力差。有效，表达空间变化性能力差。3、不能直接处理数字图像信息、不能直接处理数字图像信息4、软软硬硬件件技技术术要要求求高高，显显示示与与绘绘图图成本较高。成本较高。栅栅 格格1、结构简单，易数据交换。、结构简单，易数据交换。2、叠叠置置分分析析和和地地理理（能能有有效效表表达达空空可可变性）现象模拟较易。变性）现象模拟较易。3、利利于于与与感感遥遥数数据据的的匹匹配配应应用用和和分分析，

17、便于图像处理。析，便于图像处理。4、输出快速，成本低廉。输出快速，成本低廉。1、图图形形数数据据量量大大，数数据据结结构构不不严严密密不紧凑，需用压缩技术解决该问题。不紧凑，需用压缩技术解决该问题。2、现现象象识识别别效效果果不不如如矢矢量量方方法法，难难以表达拓扑。以表达拓扑。3、投影转换困难。、投影转换困难。4、图图形形质质量量较较低低，图图形形输输出出不不美美观观，线线条条有有锯锯齿齿，需需用用增增加加栅栅格格数数量量来来克克服服，但会增加数据文件。但会增加数据文件。地理信息系统原理GIS一、矢栅一体化概念一、矢栅一体化概念 2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二

18、章 GIS GIS 数据结构数据结构 将矢量面对目标的方法和栅格单元填充的方将矢量面对目标的方法和栅格单元填充的方法结合起来法结合起来，具体采用填满线状目标路径和充填，具体采用填满线状目标路径和充填面状目标空间的方法作为一体化数据结构的基础。面状目标空间的方法作为一体化数据结构的基础。334334423344423344234422212 以矢量的方式来以矢量的方式来组织栅组织栅格数据格数据的数据的数据结结构。构。线状地物线状地物：除记录原始取样点外，还记录路径所：除记录原始取样点外，还记录路径所通过的栅格。通过的栅格。面状地物面状地物：除记录它的多边形周边以外，还包括：除记录它的多边形周边以

19、外，还包括中间的面域栅格。中间的面域栅格。优点优点：一方面，它保留了矢量的全部性质，以目标为单一方面，它保留了矢量的全部性质，以目标为单元直接聚集所有的位置信息，并能建立拓扑关系；元直接聚集所有的位置信息，并能建立拓扑关系；另一方面，它建立了栅格与地物的关系，即路径另一方面，它建立了栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。上的任一点都直接与目标建立了联系。地理信息系统原理GIS二、三个约定和细分格网法二、三个约定和细分格网法2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构a.地面上的地面上的点状地物点状地物是地球表面上的点，它

20、仅有空间是地球表面上的点，它仅有空间位置，没有形状和面积，在计算机内部仅有一个位置位置，没有形状和面积，在计算机内部仅有一个位置数据。数据。细分格网法细分格网法（提高精度）（提高精度）：b.地面上的地面上的线状地物线状地物是地球表面的空间曲线，具有形是地球表面的空间曲线，具有形状但没有面积，它在平面上的投影是一连续不间断的状但没有面积，它在平面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组单元填满整个直线或曲线，在计算机内部需要用一组单元填满整个路径。路径。c.地面上的地面上的面状地物面状地物是地球表面的空间曲面，具有形状和面是地球表面的空间曲面，具有形状和面积，它在平面上的投影是

21、由边界包围的紧致空间和一组填满积，它在平面上的投影是由边界包围的紧致空间和一组填满路径的单元表达的边界组成。路径的单元表达的边界组成。x,yM1M2三个约定三个约定（便于组织数据）：便于组织数据）：将一对将一对x，y坐标用两个坐标用两个Morton码代替码代替-前一前一M M1 1表示该点（采样点或附加的交叉点）所在基本格网表示该点（采样点或附加的交叉点）所在基本格网的地址码，后者的地址码，后者M M2 2 表示该点对应的细分格网的表示该点对应的细分格网的MortonMorton码，码，既顾全整体定位，又保证精度。既顾全整体定位，又保证精度。地理信息系统原理GIS三、一体化数据结构设计三、一体

22、化数据结构设计2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构线性四叉树线性四叉树(Morton)是基本数据格式是基本数据格式三个约定三个约定设计点、线、面数据结构的基本依据设计点、线、面数据结构的基本依据细分格网法细分格网法保证足够精度。保证足够精度。点标识号点标识号M1M2高程高程Z10025434084432100261057725463约定约定1，点仅有位置、没有形状和面积，只要将点的坐标转化为地址码，点仅有位置、没有形状和面积，只要将点的坐标转化为地址码M1和和M2,结构简单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点结构简

23、单灵活，便于点的插入和删除，还能处理一个栅格内包含多个点状目标的情况。状目标的情况。1、点状地物和结点的数据结构、点状地物和结点的数据结构地理信息系统原理GIS2 2、线状地物的数据结构、线状地物的数据结构2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构约约定定2 2，线线状状地地物物有有形形状状但但没没有有面面积积。没没有有面面积积意意味味着着只只要要用用一一串串数数据据表表达达每每个个线线状状地地物物的的路路径径即即可可，将将该该线线状状地地物物经经过过的的所所有有栅栅格格的的地地址址全全部部记记录录下下来来。仿仿照照矢矢量量数数据据组组织

24、织的的链状双重独立式编码，以弧段为记录单位。链状双重独立式编码，以弧段为记录单位。弧标识号弧标识号起结点号起结点号终结点号终结点号中间点串（中间点串（M1,M2,Z）20078100251002658,7749,435,92,4377,439线标识号线标识号弧段标识号弧段标识号3003120078，200793003220092，20098，20099弧段的数据弧段的数据结结构构:线状地物的数据结构线状地物的数据结构:地理信息系统原理GIS3 3、面状地物的数据面状地物的数据结结构构 2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构1）弧段文件

25、）弧段文件2）带指针的二维行程码）带指针的二维行程码二维行程二维行程M码码属性值属性值005480164308314320378400448460478叶结点的属性值叶结点的属性值 改为改为指向该地物的下一个子块的循环指针指向该地物的下一个子块的循环指针二维行程二维行程M码码循环指针循环指针(属性值）属性值）0851683216313037314（属性值）（属性值）3240374440464447460（属性值）（属性值）478（属性值）（属性值）边界弧段边界弧段-形状形状面域面域循环指针循环指针指向该地物下一个子块的地址指向该地物下一个子块的地址码，并在最后指向该地物本身码，并在最后指向该地

26、物本身地理信息系统原理GIS2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构二维行程二维行程M码码循循环环指指针针(属属性性值值)0851683216313037314（属性值）（属性值）3240374440464447460（属性值）（属性值）478（属性值）（属性值）用循环指针将同属于一个目标的叶结点链接起来用循环指针将同属于一个目标的叶结点链接起来只只要要进进入入第第一一块块就就可可以以顺顺着着指指针针直直接接提提取取该该地地物物的的所所有有子子块块，从从而而避避免免像像栅栅格格数数据据那那样样为为查查询询某某一一个个目目标标需需遍遍历整

27、个矩阵，大大提高了查询速度。历整个矩阵，大大提高了查询速度。地理信息系统原理GIS3 3）面文件）面文件 2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构这这种种数数据据结结构构是是面面向向地地物物的的，具具有有矢矢量量的的特特点点。通通过过面面状状地地物物的的标标识识号号可可以以找找到到它它的的边边界界弧弧段段并并顺顺着着指指针针提提取取所所有有的的中中间间面面块块。同同时时它它又又具具有有栅栅格格的的全全部部特特性性，二二维维行行程程本本身身就就是是面面向向位位置置的的结结构构，带带指指针针的的二二维维行行程程码码中中的的Morton码码表

28、表达达了了位位置置的的相相互互关关系系，前前后后M码码之之差差隐隐含含了了该该子子块块的的大大小小。给给出出任任意意一一点点的的位位置置都都可可顺顺着着指指针针找到面状地物的标识号确定是哪一个地物。找到面状地物的标识号确定是哪一个地物。面标识号面标识号弧标识号串弧标识号串面块头指针面块头指针4000140001（属性值为（属性值为0 0）2000120001，2000220002，20003200030 04000240002（属性值为（属性值为4 4）2000220002，20004200045 54000340003（属性值为（属性值为8 8）200020003030地理信息系统原理GIS

29、4 4、复杂地物的数据结构、复杂地物的数据结构2-5 2-5 矢栅一体化数据结构矢栅一体化数据结构第二章第二章 GIS GIS 数据结构数据结构由由几几个个或或几几种种点点、线线、面面状状简简单单地地物物组组成成的的地地物物称称为为复复杂杂地地物物。例例如如将将一一条条公公路路上上的的中中心心线线、交交通通灯灯、立立交交桥桥等等组组合合为为一一个个复复杂杂地地物物，用用一一个个标标识识号号表表示示。复复杂杂地地物的数据结构如表物的数据结构如表7所示。所示。复杂地物标识号复杂地物标识号简单地物标识号简单地物标识号50008500081002510025，3000530005，3002530025

30、50009500093000630006，3000730007，4003240032 地理信息系统原理GIS2-6 2-6 三维数据结构三维数据结构第二章第二章 GIS GIS 数据结构数据结构目前目前GIS主要还停留在处理地球表面的数据，若数据是地表以下或以上，则先将它主要还停留在处理地球表面的数据，若数据是地表以下或以上，则先将它投影到投影到地表地表，再进行处理，其实质是，再进行处理，其实质是以二维的形式来模拟、处理任何数据以二维的形式来模拟、处理任何数据，在有些领域可行，在有些领域可行，但涉及到三维问题的处理时，往往力不从心。但涉及到三维问题的处理时，往往力不从心。二维二维V=f(x,y

31、)，在不同的层，在不同的层V的含义不同，当的含义不同，当V表示的是高程时，就是表示的是高程时，就是DEM。由于地形三。由于地形三维视图的原因，人们常把维视图的原因，人们常把DEM误认为是三维模型。但从本质上讲，误认为是三维模型。但从本质上讲，DEM是二维的，因为是二维的，因为它只能表示地表的信息，不能对地表内部进行有效的表示。目前，人们常把它只能表示地表的信息，不能对地表内部进行有效的表示。目前，人们常把DEM称为称为2.5维的数据模型。维的数据模型。真三维模型真三维模型V=f(x,y,z)，z是一自变量，不受是一自变量，不受x,y的影响。三维的影响。三维GIS的要求与二维的要求与二维GIS相

32、似，相似，但在数据采集，系统维护和界面设计等方面比二维但在数据采集，系统维护和界面设计等方面比二维GIS复杂得多，如三维数据的组织与重复杂得多，如三维数据的组织与重建，三维变换、查询、运算、分析、维护等方面。下面主要介绍三维数据结构。同样，建，三维变换、查询、运算、分析、维护等方面。下面主要介绍三维数据结构。同样，三维结构存在栅格和矢量两种形式。三维结构存在栅格和矢量两种形式。栅格栅格：将地理实体的三维空间分成细小单元：将地理实体的三维空间分成细小单元-体元。普遍用体元。普遍用八叉树八叉树 矢量矢量：x,y,z，抽象为点、线、面、体，面构成体。方法多种，常用，抽象为点、线、面、体，面构成体。方

33、法多种，常用三维边界表示法三维边界表示法一、概述一、概述地理信息系统原理GIS二、八叉树结构二、八叉树结构第二章第二章 GIS GIS 数据结构数据结构1 1、思想：、思想：四叉树在三维空间的推广。四叉树在三维空间的推广。将将要要表表示示的的形形体体V放放在在一一个个充充分分大大的的正正方方体体C内内，C的的边边长长为为2，不不断断用用两两个个与与XOY、XOZ的的平平面面均均分分C为为8个个子子体，并判断属性单一性。体，并判断属性单一性。当子体部分为当子体部分为V-灰结点灰结点需再需再1分为分为8。子体中无子体中无V-白结点白结点停止分割，叶结点。停止分割，叶结点。子体子体全为全为V V黑结

34、点黑结点2-6 2-6 三维数据结构三维数据结构地理信息系统原理GIS2、存贮结构、存贮结构第二章第二章 GIS GIS 数据结构数据结构1）规则八叉树）规则八叉树与与常常规规四四叉叉树树类类似似，用用9项项字字段段来来记记录录每每个个结结点点（8个个子子结结点点指指针针，1个个结结点点属属性性）。最普遍的形式，方式自然，易掌握。但指针占总存储量的。最普遍的形式，方式自然，易掌握。但指针占总存储量的94%，空间使用率低。，空间使用率低。2-6 2-6 三维数据结构三维数据结构特点特点：节省存贮空间，便于：节省存贮空间，便于某些运算，但丧失一定的灵某些运算，但丧失一定的灵活性，不便于其它遍历方式

35、活性，不便于其它遍历方式对树的结点进行存取，应用对树的结点进行存取，应用效果不佳。效果不佳。2）线性八叉树）线性八叉树 用某一预先确定的次序将八叉树转换成一个线性表，表中的每个元素与一个结点用某一预先确定的次序将八叉树转换成一个线性表，表中的每个元素与一个结点相对应。相对应。每个结点用固定的字节描述，其中某些位专门用来说明它是否为叶结点。每个结点用固定的字节描述，其中某些位专门用来说明它是否为叶结点。地理信息系统原理GIS3）一对八式的八叉树）一对八式的八叉树第二章第二章 GIS GIS 数据结构数据结构每每个个结结点点均均1分分为为8，并并标标记记为为0，1，2，3，4，5，6，7。隐隐含含

36、地地假假定定了了这这些些子结点记录存放的次序子结点记录存放的次序便于检索便于检索浪浪费费存存储储，除除非非完完全全八八叉叉树树，即即所所有有叶叶结结点点均均在在同同一一层层次次出出现现，上上层层均均为为非非叶叶结结点。点。2-6 2-6 三维数据结构三维数据结构0123701237地理信息系统原理GIS三、四面体格网三、四面体格网第二章第二章 GIS GIS 数据结构数据结构四面体格网（四面体格网（TEN）是将目标空间用紧密排列）是将目标空间用紧密排列但不重叠的不规则四面体形成的格网来表示，但不重叠的不规则四面体形成的格网来表示，其实质就是其实质就是2维维TIN结构在结构在3维空间上的扩展维空

37、间上的扩展2-6 2-6 三维数据结构三维数据结构地理信息系统原理GIS四、三维边界表示法四、三维边界表示法第二章第二章 GIS GIS 数据结构数据结构v1v2v3v4l1l2l3l4l5l6v1x1y1z1v2x2y2z2v3x3y3z3v4x4y4z4l1v1v2l2v2v3l3v3v1l4v2v4l5v4v3l6v1v4s1l1l2l3s2l2l4l5s3l5l3l6s4l3l1l4、面表：、面表：给出围成多面体某个面的各条边。给出围成多面体某个面的各条边。、当有若干个多面体时，还必须有一个当有若干个多面体时，还必须有一个对象表对象表。1、顶点表、顶点表：用来表示多面体各顶点的坐标：用

38、来表示多面体各顶点的坐标、边表：、边表：指出构成多面体某边的两个顶点；指出构成多面体某边的两个顶点；O1O1S1,s2S1,s2属性属性可避免重复表示某些点、边、可避免重复表示某些点、边、面，节约存储，便于图形显面，节约存储，便于图形显示，如公共边不重复。示，如公共边不重复。2-6 2-6 三维数据结构三维数据结构地理信息系统原理GIS5 5、扩充后的边表、扩充后的边表 第二章第二章 GIS GIS 数据结构数据结构2-6 2-6 三维数据结构三维数据结构 为表达拓扑还可将其它一些有关的内容结合到所使用的表中，如将为表达拓扑还可将其它一些有关的内容结合到所使用的表中，如将边所属的多边形边所属的

39、多边形信息结合进边表信息结合进边表中以后的形式：中以后的形式：l1v1v2s1s4l2v2v3s1s2l3v3v1s1s3l4v2v4s2s4l5v4v3s2s3l6v1v4s3s4l1v1v2l2v2v3l3v3v1l4v2v4l5v4v3l6v1v4s1l1l2l3s2l2l4l5s3l5l3l6s4l3l1l4包含包含s1,s4s1,s4公共边为公共边为l1l1的信息的信息地理信息系统原理GIS6 6、拓扑检查、拓扑检查第二章第二章 GIS GIS 数据结构数据结构2-6 2-6 三维数据结构三维数据结构数据存储后，必须检查数据的一致性、完全性，即进行拓扑检查。具体可检查下数据存储后，必

40、须检查数据的一致性、完全性，即进行拓扑检查。具体可检查下列几项：列几项：(1)顶点表中的每个顶点至少是两条边的端点；顶点表中的每个顶点至少是两条边的端点；(2)每条边至少是一个多边形的边；每条边至少是一个多边形的边；(3)每个多边形是封闭的；每个多边形是封闭的；(4)每个多边形至少有一条边是和另一个多边形共用的；每个多边形至少有一条边是和另一个多边形共用的；(5)若边表中包含了指向它所属多边形的指针，那么指向该边的指针必在相应的多若边表中包含了指向它所属多边形的指针，那么指向该边的指针必在相应的多边形中出现。边形中出现。三维边界法一般用于表示规则形体，如建筑物，对于自然界中的复杂形体如岩石三维

41、边界法一般用于表示规则形体，如建筑物，对于自然界中的复杂形体如岩石的外表，理论上可找到一在误差范围内逼近的适合平面多面体，但这种逼近受多的外表，理论上可找到一在误差范围内逼近的适合平面多面体，但这种逼近受多因素的制约。因素的制约。地理信息系统原理GIS7 7、应用、应用第二章第二章 GIS GIS 数据结构数据结构2-6 2-6 三维数据结构三维数据结构三维边界法一般用于三维边界法一般用于表示规则形体表示规则形体，如建筑物，对于自然界中的复杂形体如岩石的，如建筑物，对于自然界中的复杂形体如岩石的外表，理论上可找到一在误差范围内逼近的适合平面多面体，但这种逼近受多因素外表，理论上可找到一在误差范

42、围内逼近的适合平面多面体，但这种逼近受多因素的制约。的制约。实际上，可在形体的外表面实际上，可在形体的外表面s，测一组点，测一组点p1,p2pn坐标，再建这些点的关系，即结构坐标，再建这些点的关系，即结构图，决定顶点连接的不同方式。同样数据点，由于连接方式不同，构成的平面多面图，决定顶点连接的不同方式。同样数据点，由于连接方式不同，构成的平面多面体也不同。其中最重要的一种方法就是每个面均是三角形的平面多面体，类似体也不同。其中最重要的一种方法就是每个面均是三角形的平面多面体，类似TIN结结构。但即使这样，同一组点仍可得到不同的平面多面体。因此，需要研究拥有了哪构。但即使这样，同一组点仍可得到不

43、同的平面多面体。因此，需要研究拥有了哪些特征之后，才能更确切地逼近原来的三维形体。些特征之后，才能更确切地逼近原来的三维形体。此外，这种逼近有两种形式：此外，这种逼近有两种形式：表面表面S0的逼近：以确定后的平面多面体的表面作为对原三维形体的表面的逼近：以确定后的平面多面体的表面作为对原三维形体的表面S0的逼近，着的逼近，着眼于形体的边界表示。眼于形体的边界表示。三维形体的逼近：给出一系列的四面体，这些四面体的集合就是对原三维形体的三维形体的逼近：给出一系列的四面体，这些四面体的集合就是对原三维形体的逼近。着眼于形体的分解表示。逼近。着眼于形体的分解表示。参数函数表示法的指导思想就是利用有限的空间数据来寻求一个函数的解析表达参数函数表示法的指导思想就是利用有限的空间数据来寻求一个函数的解析表达式，用这个解析式来生成新的空间点，用以逼近原有物体式，用这个解析式来生成新的空间点，用以逼近原有物体五、参数函数表示法五、参数函数表示法