计算机地图制图数据结构课件.ppt

1、计算机地图制图计算机地图制图中国矿业大学银川学院中国矿业大学银川学院第二章 地图数据结构2.1 2.1 空间实体及其描述空间实体及其描述2.2 2.2 矢量数据结构矢量数据结构2.3 2.3 栅格数据结构栅格数据结构2.4 2.4 矢栅一体化数据结构矢栅一体化数据结构2.5 2.5 三维数据结构三维数据结构2.1 2.1 空间实体及其描述空间实体及其描述1 1）地理实体）地理实体2 2）地理实体的描述）地理实体的描述3 3）实体的空间特征）实体的空间特征4 4）实体间的关系）实体间的关系2.2 2.2 矢量数据结构矢量数据结构1 1）图形表示）图形表示2 2）获取方式）获取方式3 3）组织）组

2、织4 4）编码方式）编码方式2.3 2.3 栅格数据结构栅格数据结构1 1）图形表示）图形表示2 2）数据组织）数据组织3 3）栅格结构的建立）栅格结构的建立4 4）栅格数据编码）栅格数据编码2.4 2.4 矢栅一体化数据结构矢栅一体化数据结构1 1）矢栅一体化概念）矢栅一体化概念2 2）三个约定和细分格网法）三个约定和细分格网法3 3）一体化数据结构设计）一体化数据结构设计2.5 2.5 三维数据结构三维数据结构1 1）概述）概述2 2）八叉树结构）八叉树结构3 3）三维边界表示法）三维边界表示法本章重点本章重点点、线、面状实体；点、线、面状实体；空间数据拓扑关系；空间数据拓扑关系；矢量数据

3、结构、栅格数据结构；矢量数据结构、栅格数据结构；2.1.1 2.1.1 空间实体（地理实体）空间实体（地理实体）自然界现象和自然界现象和社会经济事件中不社会经济事件中不能再分割的单元，能再分割的单元，具有概括性，复杂具有概括性，复杂性，性，相对相对意义。意义。2.1 2.1 空间实体及其描述空间实体及其描述点状实体点状实体-0-0维维线状实体线状实体-1-1维维面状实体面状实体-2-2维维体状实体体状实体-3-3维维点状实体点状实体 有特定位置，维数为有特定位置，维数为0 0的物体。的物体。实体点实体点注记点注记点内点内点节点（节点（VertexVertex）拐点拐点线状实体线状实体 具有相同

4、属性的点的轨迹，由一系列具有相同属性的点的轨迹，由一系列有序坐标表示的物体。有序坐标表示的物体。实体长度实体长度弯曲度弯曲度方向性方向性面状实体（多边形）面状实体（多边形）是对湖泊、岛屿、地块等一类现象是对湖泊、岛屿、地块等一类现象的描述。在数据库中由的描述。在数据库中由一封闭曲线加内一封闭曲线加内点点来表示。来表示。面积范围面积范围周长周长独立性独立性内岛屿或锯齿状外形内岛屿或锯齿状外形重叠性与非重叠性重叠性与非重叠性体状实体（多边形）体状实体（多边形）描述三维空间中的现象的物体。描述三维空间中的现象的物体。体积体积周长周长内岛内岛含有弧立块或相邻块含有弧立块或相邻块断面图与剖面图断面图与剖

5、面图实体类型组合实体类型组合为地图数据库的有效建立，空间查询，为地图数据库的有效建立，空间查询，空间分析，辅助决策等空间分析，辅助决策等提供了最基本的提供了最基本的关系。关系。有助于形成标准的有助于形成标准的SQLSQL空间查询语言，空间查询语言，便于空间特征的存储，提取，查询，更便于空间特征的存储，提取，查询，更新新等。等。线线面面1 1、区域包含线：计算区、区域包含线：计算区域内线的密度，某省的水域内线的密度，某省的水系分布情况。系分布情况。2 2、线通过区域：公路上、线通过区域：公路上否通过某县。否通过某县。3 3、线环绕区域：区域边、线环绕区域：区域边界，搜索左右区域名称，界，搜索左右

6、区域名称，中国与哪些国家接壤。中国与哪些国家接壤。4 4、线与区域分离：距离、线与区域分离：距离。面面面面1 1、包含：岛、包含：岛,某省的湖泊某省的湖泊分布。分布。2 2、相合：重叠，学校服务、相合：重叠，学校服务范围与菜场服务范围重叠范围与菜场服务范围重叠区。区。3 3、相交：划分子区。、相交：划分子区。4 4、相邻：计算相邻边界性、相邻：计算相邻边界性质和长度，公共连接边界。质和长度，公共连接边界。5 5、分离：计算距离。、分离：计算距离。学校学校菜场菜场2.1.2 2.1.2 空间实体的描述空间实体的描述空间数据空间数据内容内容 数据类型数据类型数据结构数据结构几何数据（空间几何数据（

7、空间数据、图形数据）数据、图形数据）关系数据关系数据实体实体间的邻接、关联间的邻接、关联包含等相互关系包含等相互关系 属性数据属性数据各种各种属性特征和时间属性特征和时间元数据元数据 矢量、栅格、矢量、栅格、TINTIN（专用于地（专用于地表或特殊造型）表或特殊造型）RDBMSRDBMS属性表属性表-采用采用MISMIS较成熟较成熟 位置、形状、尺位置、形状、尺寸寸 、识别码（名称）识别码（名称）实体的角色、功实体的角色、功能、行为、实体能、行为、实体的衍生信息的衍生信息时间时间测量方法、编码测量方法、编码方法、空间参考方法、空间参考系等系等 空间特征：地理空间特征：地理位置和空间关系位置和空

8、间关系属性特征属性特征名称、名称、等级、类别等等级、类别等时间特征时间特征基本特征基本特征2.1.3 2.1.3 空间数据的基本特征空间数据的基本特征2.1.3 2.1.3 空间数据的类型空间数据的类型1 1）依据数据来源：）依据数据来源：地图数据、地形数据、属性数据、地图数据、地形数据、属性数据、元数据、影象数据。元数据、影象数据。2 2）依表示对象：）依表示对象：2.1.4 2.1.4 实体间空间关系实体间空间关系1 1、拓扑空间关系、拓扑空间关系 2 2、顺序空间关系（方向空间关系）、顺序空间关系（方向空间关系）3 3、度量空间关系、度量空间关系1 1）地理空间中两点间的距离有两种度量方

9、法：）地理空间中两点间的距离有两种度量方法：2 2）距离类别：）距离类别：上下左右、前上下左右、前后、东南西北。后、东南西北。a a、沿真实地球表面。、沿真实地球表面。b b、沿地球旋转椭球体距、沿地球旋转椭球体距离。离。欧氏距离、时间欧氏距离、时间距离、大地测量距离、大地测量距离。距离。1 1、定义、定义：指指图形保持连续状态图形保持连续状态下变形下变形，但图形关系不变，但图形关系不变的性质。的性质。将橡皮任意拉伸，压缩，将橡皮任意拉伸，压缩，但不能扭转或折叠。但不能扭转或折叠。拓扑关系拓扑关系 拓扑变换拓扑变换（橡皮变换）（橡皮变换）非拓扑属性非拓扑属性（几（几何属性）何属性）拓扑属性拓扑

10、属性（没发生变化的属（没发生变化的属性）性）两点间距离两点间距离一点指向另一点一点指向另一点的方向的方向弧段长度、区域弧段长度、区域周长、面积等周长、面积等一个点在一条弧段的端点一个点在一条弧段的端点 一条弧是一简单弧段一条弧是一简单弧段 一个一个点在一个区域的边界上点在一个区域的边界上一个点在一个区域的内部一个点在一个区域的内部/外部外部一个点在一个环的内一个点在一个环的内/外部外部一个面是一个简单面一个面是一个简单面一个面的连通性一个面的连通性2 2、种类：、种类：1 1）关联性关联性（不同类不同类要素间）要素间）结点与弧段：如结点与弧段：如V9V9与与L5,L6,L3L5,L6,L3多边

11、形与弧段：多边形与弧段：P2P2与与L3,L5,L2L3,L5,L22 2）邻接性邻接性：(同类同类元素之间元素之间)多边形之间、结点多边形之间、结点之间。之间。邻接矩阵：邻接矩阵：重叠：重叠：邻接：邻接：1 1 不邻接：不邻接：0 0连通矩阵：连通矩阵：重叠：重叠：连通：连通：1 1 不连通：不连通：0 03)3)方向性：一条弧段的起点、终点确定了弧方向性：一条弧段的起点、终点确定了弧段的方向。用于表达现实中的有向弧段，如段的方向。用于表达现实中的有向弧段，如城市道路单向，河流的流向等。城市道路单向，河流的流向等。4)4)包含性：包含性：指面状实体包含了哪些线、点或指面状实体包含了哪些线、点

12、或面状实体。面状实体。5)5)区域定义：多边形由一组封闭的线来定义。区域定义：多边形由一组封闭的线来定义。6)6)层次关系：相同元素之间的等级关系，武层次关系：相同元素之间的等级关系，武汉市有各个区组成。汉市有各个区组成。3 3、拓扑关系的表达：、拓扑关系的表达：拓扑关系具体可由拓扑关系具体可由4 4个关系表来表示：个关系表来表示：（1 1）面）面-链关系：链关系：面面 构成面的弧段构成面的弧段（2 2）链）链-结点关系：链结点关系：链 链两端的结点链两端的结点（3 3）结点）结点-链关系：结点链关系：结点 通过该结点的链通过该结点的链（4 4）链）链面关系：面关系：链链 左面左面 右面右面4

13、 4、拓扑关系的意义：、拓扑关系的意义：1 1）能）能清楚地反映清楚地反映实体之间的实体之间的逻辑结构关逻辑结构关系系。它比几何关系具有更大的稳定性，不。它比几何关系具有更大的稳定性，不随地图投影变化。随地图投影变化。2 2）有助于空间要素的查询有助于空间要素的查询，利用拓扑关，利用拓扑关系可以解决许多实际问题。系可以解决许多实际问题。3 3）根据拓扑关系可）根据拓扑关系可重建地理实体重建地理实体。哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题哥尼斯堡七桥问题2.2 2.2 矢量数据结构矢量数据结构2.2.1 2.2.1 图形表示图形表示2.2.2 2.2.2 获取方式获取方式1)1)外业测

14、量（电子手簿）外业测量（电子手簿）2 2）栅格数据转换（栅格数据矢量化）栅格数据转换（栅格数据矢量化）3 3）跟踪数字化）跟踪数字化2.2.3 2.2.3 矢量数据组织矢量数据组织应考虑以下问题：应考虑以下问题：矢量数据自身矢量数据自身的存贮和处理。的存贮和处理。与属性数据的与属性数据的联系。联系。矢量数据之间矢量数据之间的空间关系的空间关系(拓扑拓扑关系关系)。以点为例：以点为例：线（符号、方向）、面（符号）都有线（符号、方向）、面（符号）都有相应的相关属性（矢量结构中关于几何位相应的相关属性（矢量结构中关于几何位置坐标的编码方式）。置坐标的编码方式）。2.2.4 2.2.4 矢量数据的编码

15、方式矢量数据的编码方式1 1）实体式）实体式面条模型（面条模型（spaghettispaghetti）:以实体为单位记录坐标以实体为单位记录坐标1234567891011 1213 1415P PP PP P优点：优点：结构简单、直结构简单、直观、易实现以实体为观、易实现以实体为单位的运算和显示。单位的运算和显示。缺点：缺点：1 1、相邻多边形的公共边界被数字化并存储、相邻多边形的公共边界被数字化并存储两次，两次，造成数据冗余和碎屑多边形造成数据冗余和碎屑多边形（数据（数据不一致），浪费空间，双重边界不能精确不一致），浪费空间，双重边界不能精确匹配。匹配。2 2、自成体系，、自成体系，缺少多边

16、形的邻接信息，无缺少多边形的邻接信息，无拓扑关系拓扑关系，难以进行邻域处理。，难以进行邻域处理。3 3、岛作为一个单个图形，没有与外界多边、岛作为一个单个图形，没有与外界多边形联系。不易检查拓扑错误。形联系。不易检查拓扑错误。所以，这种结构只用于简单的制图系所以，这种结构只用于简单的制图系统中显示图形。统中显示图形。2 2）索引式（树状）索引式（树状）对所有点的坐标按顺序建坐标文件，再对所有点的坐标按顺序建坐标文件，再建点与边（线）、线与多边形的索引文件。建点与边（线）、线与多边形的索引文件。1234567891011 1213 1415P PP PP P与实体式相比：与实体式相比：优点：优点

17、：用建索引的方法用建索引的方法消除消除多边形数据的多边形数据的冗余和不一致冗余和不一致，邻接信息、岛信息可在多，邻接信息、岛信息可在多边形文件中通过是否公共弧段号的方式查边形文件中通过是否公共弧段号的方式查询。询。缺点：缺点：表达拓扑关系较表达拓扑关系较繁琐繁琐，给相邻运算、，给相邻运算、消除无用边、处理岛信息、检索拓扑关系消除无用边、处理岛信息、检索拓扑关系等带来困难，以人工方式建立编码表，工等带来困难，以人工方式建立编码表，工作量大，易出错。作量大，易出错。3 3）双重独立式编码）双重独立式编码 DIME(Dual Independent Map Encoding)DIME(Dual In

18、dependent Map Encoding)，是美国人口统计系统采用的一种编码方式，是是美国人口统计系统采用的一种编码方式，是一种一种拓扑拓扑编码结构。编码结构。1234567891011 1213 1415P PP PP P拓扑关系明确拓扑关系明确4 4）链状双重独立式编码）链状双重独立式编码以以线段线段为记录单位改为以为记录单位改为以弧段弧段为单位。为单位。1234567891011 1213 1415P PP PP P特点：特点：拓扑关系明确，以弧段为记录单位，满足拓扑关系明确，以弧段为记录单位，满足实际应用。实际应用。被一些成熟的商品化软件采用，被一些成熟的商品化软件采用，如如ARC

19、/INFOARC/INFO软件。软件。例：例：ARCARC文件文件：INFOINFO：属性表：属性表AATAAT（Arc Attribute TableArc Attribute Table）2.3 2.3 栅格数据结构栅格数据结构2.3.1 2.3.1 图形表示图形表示 用密集正方形（或三角用密集正方形（或三角形，多边形）将地理区形，多边形）将地理区域域划分划分为网格阵列。为网格阵列。位置由行，列号定义，位置由行，列号定义，属性为栅格单元的值。属性为栅格单元的值。栅格数据的栅格数据的比例尺比例尺就是就是栅格栅格(象元象元)的大小与地的大小与地表相应单元的大小之比表相应单元的大小之比。点：点：

20、单个单个栅格栅格线：相邻线：相邻栅格组栅格组面：栅面：栅格片格片2.3.2 2.3.2 栅格数据组织栅格数据组织针对一个栅格单元对应多个属性值的针对一个栅格单元对应多个属性值的多层栅格多层栅格文件文件。组织方法组织方法2.3.3 2.3.3 栅格结构的建立栅格结构的建立1 1）建立途径）建立途径手工获取手工获取扫描仪扫描扫描仪扫描 矢量数据转换矢量数据转换遥感影像遥感影像数据数据 格网格网DEMDEM数据数据2 2）栅格系统的确定）栅格系统的确定 实质是栅格坐标系实质是栅格坐标系的确定的确定-坐标系原点和坐标系原点和坐标轴坐标轴的确定。的确定。起始坐标应与国家起始坐标应与国家基本比例尺地形图公

21、里基本比例尺地形图公里网的交点相一致，并分网的交点相一致，并分别别采用公里网的纵横坐采用公里网的纵横坐标轴作为栅格系统的坐标轴作为栅格系统的坐标轴标轴。3 3）栅格单元尺寸的确定）栅格单元尺寸的确定l原则：应能原则：应能有效地逼近有效地逼近空间对象的分布特征，空间对象的分布特征，又减少数据的冗余度又减少数据的冗余度。l方法：用保证最小多边方法：用保证最小多边形的精度标准来确定尺形的精度标准来确定尺寸经验公式：寸经验公式：h h为栅格单元为栅格单元边长边长 AiAi为区域所有为区域所有多边形的面积多边形的面积。4 4）栅格代码（属性值）的确定）栅格代码（属性值）的确定中心点法中心点法面积占优法面

22、积占优法重要性法重要性法长度占优法长度占优法2.3.4 2.3.4 栅格数据编码栅格数据编码1 1）直接栅格编码）直接栅格编码 将栅格数据看作一将栅格数据看作一个数据矩阵，个数据矩阵，逐行记录逐行记录代码数据。代码数据。1 1）每行都从左到右记录：）每行都从左到右记录：AAAAABBBAABBAABBAAAAABBBAABBAABB2 2）奇数行从左到右，偶）奇数行从左到右，偶数行从右到左；数行从右到左；特点特点：直观、基本，没：直观、基本，没进行任何压缩数据处理。进行任何压缩数据处理。将数据表示成更紧凑的格式以减少存储将数据表示成更紧凑的格式以减少存储空间的一项技术。分为：空间的一项技术。分

23、为：无损压缩无损压缩：在编码过程中信息没有丢失，经：在编码过程中信息没有丢失，经过解码可恢复原有的信息过解码可恢复原有的信息-信息保持编码。信息保持编码。有损压缩有损压缩：为最大限度压缩数据，在编码中：为最大限度压缩数据，在编码中损失一些认为不太重要的信息，解码后，这损失一些认为不太重要的信息，解码后，这部分信息无法恢复。部分信息无法恢复。-信息不保持编码。信息不保持编码。数据压缩数据压缩2 2）行程编码（变长编码）行程编码（变长编码）将原图表示的数据将原图表示的数据矩阵变为矩阵变为数据对数据对：1 1）属性码，长度，行）属性码，长度，行号（可不要）号（可不要）2 2）属性码，点位）属性码，点

24、位特点：特点：数据量增加不明数据量增加不明显，压缩率高，易于操显，压缩率高，易于操作，适用于区域面积较作，适用于区域面积较大专题图。大专题图。3 3）块码（游程编码向二维的扩展）块码（游程编码向二维的扩展）采用采用方形区域方形区域作为记录作为记录单元，每个记录单元包括相单元，每个记录单元包括相邻的若干栅格。依次扫描，邻的若干栅格。依次扫描，编过的不重复。编过的不重复。数据对组成数据对组成：（初始行、：（初始行、列，半径，属性值）列，半径，属性值）特点：特点：具有具有可变分辨率可变分辨率，分，分辨率低，压缩比高，辨率低，压缩比高，随图形随图形复杂程度的提高而降低。复杂程度的提高而降低。（1,1,

25、1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7)4 4）链式编码、）链式编码、FreemanFreeman链码、边界链码链码、边界链码 将栅格数据（线状地物面域边界）表示为将栅格数据（线状地物面域边界）表示为矢量链矢量链的记录。的记录。优点：优点：便于便于面积、长度、面积、长度、转折方向和边界、线段转折方向和边界、线段凹凸度的凹凸度的计算。计算。缺点：缺点：不易做边界合并，不易做边界合并，插入操作、编辑较困难。插入操作、编辑较困难。区域空间分析困难，区域空间分析困难，相相邻区域边界被邻区域边界被重复存储。重复存储。5 5）四叉树编码）四叉树编码 四叉树概述：一种四叉树概述：

26、一种可变分率可变分率的的非均匀网非均匀网格格系统。系统。是最有效的栅格数据压缩编码方法是最有效的栅格数据压缩编码方法之一之一。l基本思想：基本思想：将将2 2n n2 2n n象元组成象元组成的图像的图像(不足的用背景不足的用背景补上补上)按四象限进行递按四象限进行递归分割，判断属性是否归分割，判断属性是否单一。单一。最后得到一颗四最后得到一颗四分叉的倒向树。分叉的倒向树。l树形表示：树形表示：用一倒立树表示用一倒立树表示这种分割和分割结果。这种分割和分割结果。根：整个区域根：整个区域高：深度、分几级，高：深度、分几级，几次分割几次分割叶：不能再分割的块叶：不能再分割的块树叉：还需分割的块树叉

27、：还需分割的块 每个树叉均有每个树叉均有4 4个个分叉，叫四叉树。分叉，叫四叉树。l编码方法编码方法：常规四叉树：常规四叉树：记录叶结记录叶结点，中间结点，结点之点，中间结点，结点之间用指针联系。间用指针联系。每个结点需要每个结点需要6 6个变量：个变量：父结点指针、四个子结点父结点指针、四个子结点的指针和本结点的属性值的指针和本结点的属性值。线性四叉树：线性四叉树：记录叶结记录叶结点的点的位置，深度，位置，深度，属性。属性。地址码（定位码、地址码（定位码、MortonMorton码）码）指针不仅指针不仅增加了数据的增加了数据的存储量存储量，还增加了操作，还增加了操作的的复杂性复杂性，并不广泛

28、用并不广泛用于存储数据于存储数据。存贮量小，只对叶结存贮量小，只对叶结点编码，直接寻址，点编码，直接寻址，定位码容易存储和执定位码容易存储和执行实现集合相加等组行实现集合相加等组合操作。合操作。四进制四进制MortonMorton码码方法方法1 1：四叉树：四叉树从上而下从上而下由由叶结点找叶结点找MortonMorton码。码。A A、分割一次，增加一位数、分割一次，增加一位数字，大分割在前，小分割在字，大分割在前，小分割在后。所以，后。所以，码的位数表示分码的位数表示分割的次数割的次数。B B、每一个位均是不大于每一个位均是不大于3 3的的四进制数，表达位置四进制数，表达位置。由由Mort

29、onMorton找出四叉树叶结点找出四叉树叶结点的具体位置。的具体位置。方法方法2 2：四叉树：四叉树自下而上自下而上合并的方法。合并的方法。1 1）计算每个栅格对应的）计算每个栅格对应的MQMQMQ=2MQ=2*Ib+Jb Ib+Jb 其始行列号从其始行列号从0 0计。计。2)2)按码的升序排成线性按码的升序排成线性表，放在连续的内存块中。表，放在连续的内存块中。3 3）依次检查每四个相邻）依次检查每四个相邻的的MQMQ对应的属性值，相同对应的属性值，相同合并（不同码位去掉），合并（不同码位去掉），不同则存盘不同则存盘,直到没有能直到没有能够合并的子块为止。够合并的子块为止。十进制十进制Mo

30、rtonMorton码码按位操作按位操作的方法。的方法。如行为如行为2 2、列为、列为3 3的栅格的的栅格的MDMD步骤：步骤：(1)(1)行、列号为二进制行、列号为二进制 (2)I(2)I行行J J列交叉列交叉 (3)(3)再化为十进制再化为十进制.实质上是按左上、右实质上是按左上、右上、左下、右下的顺序，上、左下、右下的顺序，从零开始对每个栅格进行从零开始对每个栅格进行自然编码。自然编码。把一幅把一幅2n2n2n2n的图像压缩成线性四叉树的过程：的图像压缩成线性四叉树的过程：1 1、按、按MortonMorton码把图象读码把图象读入一维数组。入一维数组。2 2、相邻的四个象元比较，、相邻

31、的四个象元比较，一致的合并，只记录第一一致的合并，只记录第一个象元的个象元的MortonMorton码。循环码。循环比较所形成的大块，相同比较所形成的大块，相同的再合并，直到不能合并的再合并，直到不能合并为止。为止。3 3、进一步用游程长度编、进一步用游程长度编码压缩。压缩时只记录第码压缩。压缩时只记录第一个象元的一个象元的MortonMorton码。码。1 1、按按MortonMorton码读入一维数组。码读入一维数组。MortonMorton码：码：0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514

32、 15象元值：象元值：A A A B A A B B A A A A B B B BA A A B A A B B A A A A B B B B2 2、四相邻象元合并，只记录第一个象元的四相邻象元合并，只记录第一个象元的MortonMorton码。码。0 1 2 3 4 5 6 7 8 120 1 2 3 4 5 6 7 8 12A A A B A A B B A BA A A B A A B B A B3 3、用游程长度编码压缩。用游程长度编码压缩。0 3 4 6 8 120 3 4 6 8 12A B A B A B A B A B A B 四叉树优缺点四叉树优缺点优点：优点：1 1）占

33、用空间比网络法要少得多，是一种）占用空间比网络法要少得多，是一种非非冗余表示法冗余表示法。2 2）四叉树具有）四叉树具有可变率或多重分辩率可变率或多重分辩率的特点的特点使得它有很好的应用前景，使得它有很好的应用前景，适用于适用于处理处理凝凝聚性聚性或呈或呈不均匀的不均匀的块状分布的块状分布的空间数据，空间数据，但但不适用于不适用于连续表面或线状地物连续表面或线状地物。缺点：缺点：1 1）矢）矢/栅正反变换还不理想。栅正反变换还不理想。2 2）建立四叉树建立四叉树耗费机时耗费机时很多。很多。3 3）修改费事。）修改费事。4 4）未能直接表示未能直接表示物体间的物体间的拓扑关系拓扑关系。5 5）转

34、换的不稳定性（）转换的不稳定性（滑动变异滑动变异）。6 6）无内在相关性无内在相关性。矢量、栅格数据结构的矢量、栅格数据结构的选择选择 应根据应根据应用目的应用目的和和应用特点应用特点、可能获得的、可能获得的数据精度数据精度以及以及软件和硬件软件和硬件配置情况，选择合适配置情况，选择合适的数据结构。的数据结构。栅格结构栅格结构:大范围小比例尺大范围小比例尺的的自然资源、环境、自然资源、环境、农林业农林业等区域问题的研究。等区域问题的研究。矢量结构：城市矢量结构：城市分区分区或或详细规划详细规划、土地管理、土地管理、公用事业公用事业管理管理等方面的应用。等方面的应用。2.42.4 矢栅一体化数据

35、结构矢栅一体化数据结构2.4.1 2.4.1 以矢量以矢量的方式来的方式来组织栅格组织栅格数数据的数据结构：据的数据结构：线状地物：记录原始取样点和路径线状地物：记录原始取样点和路径所通过的栅格。所通过的栅格。面状地物：记录多边形周边以外及面状地物：记录多边形周边以外及中间的面域栅格。中间的面域栅格。保留了矢量的全部性质，也建立了保留了矢量的全部性质，也建立了栅格与地物的关系，即路径上的任栅格与地物的关系，即路径上的任一点都直接与目标建立了联系。一点都直接与目标建立了联系。将将矢量矢量面对目面对目标标的方的方法和法和栅栅格元子格元子充填充填的的方法结方法结合。合。a.a.点状地物点状地物是地球

36、表面上的点仅有空间位置，是地球表面上的点仅有空间位置，没有形状和面积，在计算机内部仅有一个位置没有形状和面积，在计算机内部仅有一个位置数据。数据。2.4.2 2.4.2 三个约定和细分格网法三个约定和细分格网法b.b.线状地物线状地物是地球表面的空间曲线，有形状是地球表面的空间曲线，有形状但没有面积，在平面上的投影是一连续不间但没有面积，在平面上的投影是一连续不间断的直线或曲线，在计算机内部需要用一组断的直线或曲线，在计算机内部需要用一组元子填满整个路径。元子填满整个路径。c.c.面状地物面状地物是地球表面的空间曲面，具有形状是地球表面的空间曲面，具有形状和面积，在平面上的投影是由边界包围的紧

37、致和面积，在平面上的投影是由边界包围的紧致空间和一组填满路径的元子表达的边界组成。空间和一组填满路径的元子表达的边界组成。为提高栅格表示精度，为提高栅格表示精度，采用采用细分格网法细分格网法：将一对将一对X,YX,Y坐标用两个坐标用两个MortonMorton码代替：码代替：前一前一M M1 1表示该点（采样表示该点（采样点或附加的交叉点）所点或附加的交叉点）所在基本格网的地址码，在基本格网的地址码，后者后者M M2 2 表示该点对应的表示该点对应的细分格网的细分格网的MortonMorton码，码，既顾全整体定位，又保既顾全整体定位，又保证精度。证精度。2.4.3 2.4.3 一体化数据结构

38、设计一体化数据结构设计 线性四叉树线性四叉树(Morton)(Morton)是基本数据格式，是基本数据格式，三三个约定个约定设计点、线、面数据结构的基本依据，设计点、线、面数据结构的基本依据，细分格网法细分格网法保证足够精度。保证足够精度。1 1）点状地物和结点点状地物和结点的数的数据结构：点仅有位置、据结构：点仅有位置、没有形状和面积，将点没有形状和面积，将点的坐标转化为地址码的坐标转化为地址码M1M1和和M2,M2,便于点的插入和便于点的插入和删除和处理栅格内含多删除和处理栅格内含多个点状目标的情况。个点状目标的情况。2 2）线状地物和结线状地物和结点点的数据结构：的数据结构：有有形状但没

39、有面积，形状但没有面积，没有面积意味着只没有面积意味着只要用要用一串数据表达一串数据表达每个线状地物的路每个线状地物的路径径即可，即可，将该线状将该线状地物经过的所有栅地物经过的所有栅格的地址全部记录格的地址全部记录下来下来。仿照矢量数。仿照矢量数据组织的链状双重据组织的链状双重独立式编码，以弧独立式编码，以弧段为记录单位。段为记录单位。3 3）面状地物面状地物的数据结构：的数据结构：弧段文件弧段文件边界弧段边界弧段-形状形状带指针的二维行程码带指针的二维行程码 面域面域 叶结点的叶结点的属性值属性值改为改为指向该地物的下一个子块的指向该地物的下一个子块的循环指针循环指针。循环指针循环指针指向

40、该地物指向该地物下一个子块的地址码，下一个子块的地址码，并在最后指向该地物并在最后指向该地物本身。本身。只要进入第一块就可以顺着指针直接提取只要进入第一块就可以顺着指针直接提取该地物的所有子块，从而避免像栅格数据那样该地物的所有子块，从而避免像栅格数据那样为查询某一个目标需遍历整个矩阵，为查询某一个目标需遍历整个矩阵，大大提高大大提高了查询速度了查询速度。4 4）复杂地物复杂地物的数据结构：的数据结构：由几个或几种点、线、面状简单地物组成由几个或几种点、线、面状简单地物组成的地物的地物称为复杂地物。例如将一条公路上的中称为复杂地物。例如将一条公路上的中心线、交通灯、立交桥等组合为一个复杂地物，

41、心线、交通灯、立交桥等组合为一个复杂地物，用一个标识号表示。用一个标识号表示。矢量和栅格的转换矢量和栅格的转换矢量矢量栅格栅格点和线地物点和线地物栅格栅格 根据点或线的某个属性对相应栅格点进行根据点或线的某个属性对相应栅格点进行赋值。赋值。多边形多边形 需要进行填充，填充则要基于点和多边需要进行填充，填充则要基于点和多边形的空间关系判断形的空间关系判断 扫描线算法（相切的情形需要区分）扫描线算法（相切的情形需要区分）基基于于拓拓扑扑多多边边形形的的边边界界代代数数算算法法栅格到矢量的转换栅格到矢量的转换abcd(a)aabc(b)abcc(c)abac(d)abcb(e)abca(f)abbc

42、(e)abba(g)将每个栅格点视为一个方形区域将每个栅格点视为一个方形区域因此，总是转换得到多边形地物因此，总是转换得到多边形地物思路：区分不同的节点和边界类型（及思路：区分不同的节点和边界类型（及2 2*2 2栅格区域内栅格数值的组合）栅格区域内栅格数值的组合）aabb(a)abab(b)aaab(c)aaba(d)abbb(e)abaa(f)节点节点边界点边界点2.5 2.5 三维数据结构三维数据结构 目前计算机地图制图主要还停留在处理目前计算机地图制图主要还停留在处理地球表面的数据，若数据是地表以下或以上，地球表面的数据，若数据是地表以下或以上，则先将它投影到地表，再进行处理，其实质则

43、先将它投影到地表，再进行处理，其实质是是以二维的形式来模拟、处理任何数据以二维的形式来模拟、处理任何数据，在，在有些领域可行，但涉及到三维问题的处理时，有些领域可行，但涉及到三维问题的处理时，往往力不从心往往力不从心。二维二维V=f(x,y)V=f(x,y)在不同的层在不同的层V V的含义不同，的含义不同，当当V V表示的是高程时，就是表示的是高程时，就是DEMDEM。真三维模型真三维模型V=f(x,y,z)V=f(x,y,z)，z z是一自是一自变量，不受变量，不受x,yx,y的影响。在数据采集，的影响。在数据采集，系统维护和界面设计等方面比二维复杂系统维护和界面设计等方面比二维复杂得多，同

44、样，三维结构存在栅格和矢量得多，同样，三维结构存在栅格和矢量两种形式。两种形式。栅格栅格：将地理实体的三维空间分成细小：将地理实体的三维空间分成细小单元单元-体元。普遍用体元。普遍用八叉树八叉树。矢量矢量：x,y,zx,y,z，抽象为点、线、面、体，抽象为点、线、面、体，面构成体。方法多种，常用面构成体。方法多种，常用三维边界表三维边界表示法示法。2.5.2 2.5.2 八叉树：八叉树：1 1）思想：）思想：四叉树在三维空间的推广四叉树在三维空间的推广。将要表示的形体将要表示的形体V V放在一个充分大的正放在一个充分大的正方体方体C C内，内，C C的边长为的边长为2 2n n，不断用两个与，

45、不断用两个与XOYXOY、XOZXOZ的平面均分的平面均分C C为为8 8个子体，并判断属性单个子体，并判断属性单一性。一性。2 2）存储结构：）存储结构：l规则八叉树规则八叉树 与常规四叉树类似，用与常规四叉树类似，用1010项字段来记项字段来记录每个结点（录每个结点（8 8个子结点指针，个子结点指针，1 1个父结个父结点指针，点指针，1 1个结点属性个结点属性）。）。l线性八叉树线性八叉树 用某一预先确定的次序将八叉树转换成用某一预先确定的次序将八叉树转换成线性表，表中的每个元素与一个结点相对线性表，表中的每个元素与一个结点相对应。每个结点用固定的字节描述，其中某应。每个结点用固定的字节描

46、述，其中某些位专门用来说明它是否为叶结点。些位专门用来说明它是否为叶结点。特点：特点：节省存贮空间节省存贮空间，便于某些运算，但丧失，便于某些运算，但丧失一定的灵活性，一定的灵活性，不便于其它遍历方式不便于其它遍历方式对树的结对树的结点进行存取，点进行存取，应用效果不佳应用效果不佳。l一对八式八叉树一对八式八叉树 每个结点均每个结点均1 1分为分为8 8，并标记为，并标记为0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7。隐含地假定了这些子结点记录存。隐含地假定了这些子结点记录存放的次序放的次序-便于检索但浪费存储便于检索但浪费存储，除非完全，除非完全八叉树，即所有叶结点均在同一

47、层次出现，上八叉树，即所有叶结点均在同一层次出现，上层均为非叶结点。层均为非叶结点。2.5.3 2.5.3 三维边界表示法三维边界表示法6 6、拓扑检查、拓扑检查 数据存储后，必须检查数据的一致性、完全数据存储后，必须检查数据的一致性、完全性性。(1)(1)顶点表中每个顶点至少是两条边的端点；顶点表中每个顶点至少是两条边的端点；(2)(2)每条边至少是一个多边形的边；每条边至少是一个多边形的边；(3)(3)每个多边形是封闭的；每个多边形是封闭的；(4)(4)每个多边形至少有一条边是和另一个多边每个多边形至少有一条边是和另一个多边形共用的；形共用的；(5)(5)若边表中包含了指向它所属多边形的指

48、针，若边表中包含了指向它所属多边形的指针，则指向该边的指针必在相应的多边形中。则指向该边的指针必在相应的多边形中。7 7、应用、应用 三维边界法一般用于三维边界法一般用于表示规则形体表示规则形体，对于，对于自然界中的复杂形体，理论上可找到在误差范自然界中的复杂形体，理论上可找到在误差范围内逼近的适合多面体，但受多因素的制约。围内逼近的适合多面体，但受多因素的制约。对于不规则形体，可在形体的外表面测一对于不规则形体，可在形体的外表面测一组点组点p1,p2p1,p2的坐标再建这些点的关系，决定的坐标再建这些点的关系，决定顶点连接的不同方式。同一组点可得到不同的顶点连接的不同方式。同一组点可得到不同

49、的平面多面体。需研究拥有了哪些特征才能更确平面多面体。需研究拥有了哪些特征才能更确切地逼近原来的三维形体。切地逼近原来的三维形体。这种逼近有两种形式：这种逼近有两种形式：表面表面S0S0的逼近的逼近：以确定后的平面多面：以确定后的平面多面体的表面作为对原三维形体的表面体的表面作为对原三维形体的表面S0S0的逼的逼近，着眼于形体的近，着眼于形体的边界边界表示。表示。三维形体的逼近三维形体的逼近：给出一系列的四面：给出一系列的四面体，这些四面体的集合就是对原三维形体体，这些四面体的集合就是对原三维形体的逼近。着眼于的逼近。着眼于形体形体的分解表示。的分解表示。作业：作业：1.1.空间数据空间数据有那些基本有那些基本特征？特征？2.2.利用关系利用关系表来表达下表来表达下图的空间拓图的空间拓扑关系。扑关系。ebc c41 1325AB BC C76D Dada:a:结结点号点号A:A:多边多边形号形号1:1:弧弧段号段号 3.3.比较矢量和栅格数据结构的优缺点？比较矢量和栅格数据结构的优缺点？4.4.建立下面栅格矩阵的游程编码结构。建立下面栅格矩阵的游程编码结构。0 2 2 5 5 5 2 2 2 2 2 5 2 2 2 2 3 3 0 0 2 3 3 3 0 0 3 3 3 3 0 0 0 3 3 3