第三章 空间数据结构

第三章空间数据结构与编码栅格数据结构及编码矢量数据结构及编码矢栅数据结构转换矢栅一体化数据结构

空间数据结构与数据编码1.概念

空间数据结构：指适合于计算机系统存储、管理和处理的地学图形的逻辑结构，是地理实体的空间排列方式和相互关系的抽象描述。

空间数据编码：为实现空间数据的计算机存储、处理和管理，将空间实体的一定的数据结构转换为适合计算机操作的过程。

图形数据属性数据编码(数据结构)空间实体数据存入计算机栅格数据结构：应用与图像处理系统和GIS中。矢量数据结构：主导了CAD系统和有着强大制图功能的GIS。一、基于规则格网空间数据模型的数据结构(栅格数据结构)（一）概念栅格数据结构是最简单最直观的空间数据结构，又称网格结构或像元结构。将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个像元或者像素，有行、列号定义，并包含一个代码，表示该网格的属性值或者量值，或者仅仅包含指向其它属性记录的指针。（一）概念栅格数据结构实际就是像元阵列，每个像元由行列确定它的位置。由于栅格结构是按照一定的规则排列的，所表示的实体的位置很容易隐含在文件的存储结构中，且行列坐标可以很容易的转为其他坐标系下的坐标。在文件中每个代码本身明确代表实体的属性或属性编码。点用一个栅格单元表示；线状地物沿线走向的一组相邻栅格单元表示，每个栅格单元最多只有两个相邻单元在线上；面或区域用记有区域属性的相邻栅格单元的集合表示，每个栅格单元可有多于两个的相邻单元同属一个区域。

点线面（一）概念（二）基本特征点有大小、地理空间离散。大小由行列号决定，划分程度决定点大小、点数多少、表达内容的复杂程度及精度高低。属性特征显性表示。可以直接看到属性，并多以颜色、代码或灰度表示。面向位置、感觉微观

位置由行列号决定，每个位置都有相应的数据。（三）栅格数据的组织不同类型的地理实体分层编排，每层只有单一的类型。一个栅格单元只有一个属性代码。空间数据库22222aaaaa22土壤植被组织方法（三）栅格数据的组织数据文件像元1X坐标Y坐标层1属性层2属性...层n属性像元2…像元n数据文件层1X坐标Y坐标属性值像元2...像元n层2…层n像元1数据文件层1属性值像元1坐标像元2坐标…多边形2...多边形n层2…层n多边形1像元n坐标（四）栅格结构的建立1、

手工获取，专题图上划分均匀网格，逐个决定其网格代码。2、扫描仪扫描专题图的图像数据{行、列、颜色（灰度）}，定义颜色与属性对应表，用相应属性代替相应颜色，得到（行、列、属性）再进行栅格编码、存贮，即得该专题图的栅格数据。3、

由矢量数据转换而来。4、

遥感影像数据，对地面景象的辐射和反射能量的扫描抽样，并按不同的光谱段量化后，以数字形式记录下来的象素值序列。5、

格网DEM数据，当属性值为地面高程，则为格网DEM，通过DEM内插得到。一）建立途径（四）栅格结构的建立二）栅格系统的建立1、

栅格坐标系的确定表示具有空间分布特征的地理要素，不论采用什么编码系统，什么数据结构都应在统一的坐标系统下，而坐标系的确定实质是坐标系原点和坐标轴的确定。由于栅格编码一般用于区域性GIS，原点的选择常具有局部性质，但为了便于区域的拼接，栅格系统的起始坐标应与国家基本比例尺地形图公里网的交点相一致，并分别采用公里网的纵横坐标轴作为栅格系统的坐标轴。（四）栅格结构的建立二）栅格系统的建立2、

栅格单元的尺寸1）原则：应能有效地逼近空间对象的分布特征，又减少数据的冗余度。格网太大，忽略较小图斑，信息丢失。2）方法：用保证最小多边形的精度标准来确定尺寸经验公式：

h为栅格单元边长

Ai为区域所有多边形的面积。每个栅格元素只能取一个值，实际上一个栅格可能对应于实体中几种不同属性值，存在栅格数据取值问题ABC

D（四）栅格结构的建立三）栅格属性值的确定1、中心点法用处于栅格中心处的地物类型或现象特性决定栅格代码。中心点法常用于具有连续分布特性的地理要素，如降雨量分布、人口密度图等。BDDDBBDCBBCCBBAAABC

D三）栅格属性值的确定2、面积占优法以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码。用于分类较细，地物类别斑块较小的情况。

BDDDBBDCBBCCBBAAABC

D三）栅格属性值的确定3、长度占优法将网格中心画一横线，用横线所占最长部分属性值作为栅格属性BDDDBBDCBBCCBBAAABC

D三）栅格属性值的确定4、重要性法突出某些主要属性，只要在栅格中出现就把该属性作为栅格属性DDDDBDDCBBAABBAAABC

D三）栅格属性值的确定5、百分比法根据矩形区域内各地理要素所占面积的百分比数确定单元的取值。DDDDBDDCBBAABBAAABC

D三）栅格属性值的确定（五）栅格数据编码方式直接栅格编码压缩编码方法链码（ChainEncoding）游程编码（Run-lengthEncoding）块状编码（BlockEncoding）四叉树编码（QuandtreeEncoding）

（五）栅格数据结构类型（1）直接栅格编码

最简单最直观而又非常重要的一种栅格结构编码方法。把规则格网平面作为一个二维矩阵进行数学表达，每个栅格是具有行、列位置的矩阵元素，该空间实体属性编码值赋予矩阵元素。

逐行或逐列记录代码。2221177722221777222222222227777744447777（1）直接栅格编码

(1,1,2),(1,2,2),(1,3,2),(1,4,1),(1,5,1),(1,6,7),(1,7,7),(1,8,7),(2,1,2),(2,2,2),(2,3,2),……如果行列号记录在专门文件中，则只记录属性值：（2,2,2,1,1,7,7,7,2,2,2,2,1,7,7,7……）优点：1易于实现用循环语句编程，实现快速运算2易于实现空间属性的分解与分类，易于实现空间分析中叠加等操作缺点：数据存储量大基本要素包括：行，列，属性值（N，M，Xij）其中行、列值隐性，属性值显性。（1）直接栅格编码

（2）费尔曼链码（边界编码）

将线状地物或区域边界表示为：由某一起始点和某些基本方向上的单位矢量链组成。前两个字母表示起点的行列号，从第三个数字开始每个数字表示单位矢量的方向。70162543单位矢量的长度为一个栅格单元，后续点可能位于前继点8个基本方向上。（2）费尔曼链码（边界编码）

具体编码过程：起始点的寻找一般遵守从上到下、从左到右的原则。当发现没有记录过的点且数值也不为零时，就是这一条线或边界的起点，记下该地物的特征码和行列号；然后按顺时针方向寻找，找到相邻的等值点，并按八个方向编码。如遇到不能闭合的线段，结束后可返回到起始点再开始寻找下一个线段。已记录过的栅格单元，可将属性代码置零，以免重复编码。2850002000008020000002000000020005502055555020555552000550020000000（2）费尔曼链码（边界编码）特征码高程起止行列链码2100m1，44,5,4,5,5,45200m4，72,4,4,6,5,6,7,0,2,2,170162543454545424465670221（2）费尔曼链码（边界编码）优缺点：数据压缩率强，便于计算长度，面积，转折方向的凸凹度，易于储存。但难于实现叠置运算，不便于合并插入操作。对局部改动涉及到整体结构。适于对曲线和边界进行编码。（2）费尔曼链码（边界编码）（3）游程（行程）编码

基本思路：对一个栅格图形，常常有行（列）方向上相邻的若干栅格单元具有相同的属性代码，因而可采用某种方法压缩那些重复代码内容。编码方案：只是在各行（列）栅格单元的代码发生变化时依次记录该代码以及相同代码重复的个数或者记录代码发生变化的位置。（3）游程（行程）编码

游程：栅格数据矩阵中相邻并属性相同的栅格视为一游程，以游程为单位记录数据。2228800058888770第一行：4个游程第二行：3个游程适于对块状地物的栅格数据进行压缩编码编码方式：(gk，lk)gk—栅格属性值lk—游程终止列号或长度K=1,2,3,4…..m(m<n)分为游程终止编码和游程长度编码

（3）游程（行程）编码

(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)游程终止编码（3）游程（行程）编码

（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)游程长度编码：（3）游程（行程）编码

特点：属性的变化愈少，游程愈长，即压缩比的大小与图的复杂程度成反比。

优点：数据压缩率高，易于实现叠加，检索和合并运算。缺点：适合类型区面积较大的专题图、遥感影像分类集中的分类图，不适合类型连续变化或类型区分散的分类图。（3）游程（行程）编码

（4）块状编码是将游程长度编码扩展到二维的情况，采用正方形区域为单元对块状地物的栅格数据进行编码，实质是把栅格阵列中同一属性方形区域各元素映射成一个元素系列。每个记录单元包含相邻若干栅格，数据结构由初始位置和半径，在加上记录单元的代码组成。编码方式：（行号，列号，半径，代码）0225555522222555000003332222335500233355003333530003333300003333（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。（4）块状编码特点：1、面状地物所能包含的正方形越大，多边形边界越简单，块码编码效率超高；2、图形比较碎，多边形边界复杂的图形，数据压缩率低；3、利于计算面积、合并插入等操作。（4）块状编码（5）四叉树编码（QuadtreeCode）四叉树概述：四叉树又称为四元树或四分树，是最有效的栅格数据压缩编码方法之一，绝大部分图形操作和运算都可以直接在四叉树结构上实现，四叉树编码即压缩了数据量，又可大大提高图形操作的效率。1、基本思想：将2n×2n象元组成的图像(不足的用背景补上)按四个象限进行递归分割，并判断属性是否单一，单一：不分。不单一：递归分割。最后得到一颗四分叉的倒向树。（5）四叉树编码（QuadtreeCode）2、四叉树的树形表示：用一倒立树表示分割和分割结果。根：整个区域高：深度、分几级，几次分割叶：不能再分割的块树叉：还需分割的块。0123AAAAABBBAABBAABB000004440004444400444488004448882244888822248888222288882222888800004404440444848244824221）常规四叉树及编码原始栅格四叉树图1）常规四叉树及编码四叉树编码的树状表示NWNESWSE004482220000444444484442(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)0层1层2层3层记录这棵树的叶结点外，中间结点，结点之间的联系用指针联系，每个结点需要6个变量：父结点指针、四个子结点的指针和本结点的属性值。对一幅2N

×2N的栅格阵列，最大深度为N，可能有的层次为0，1，2，…，N，最大层数为N+1.那么，每层的栅格宽度为：

2（最大深度-当前层次）反映了所在叶结点表示的正方形集合的大小。1）常规四叉树及编码缺点：所占空间比较大，不仅要记录每个结点，还要记录一个前趋结点和四个后继点，以及反映结点之间联系，对栅格数据进行运算时，还要作遍历树结点的运算，增加操作复杂性。1）常规四叉树及编码指针不仅增加了数据的存储量，还增加了操作的复杂性：如层次数（分割次数）由从父结点移到根结点的次数来确定，结点所代表的图像块的位置需要从根节点开始逐步推算下来。所以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。2)线性四叉树及编码以四叉树的方式组织数据，但不以四叉树方式存储数据。通过编码四叉树的叶结点表示数据的层次和空间关系。叶结点具有一个反映位置的关键字，亦称位置码。实质是把原来大小相等的栅格集合转换成大小不等的正方形集合，对不同尺寸和位置的正方形集合赋予一个位置码。2)线性四叉树及编码

只存贮最后叶结点信息。包括：结点号、结点位置、深度、本节点的属性或灰度值象限划分：

0123(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

00000000000000001100000011110000111110001111000000000000000000002)线性四叉树及编码2）线性四叉树及编码（1）基于深度和层次码的线性四叉树编码

它通过记录叶结点的深度码和层次码来描述叶结点的位置，2N为层次码。如图中叶结点（7）的编码为：层次码深度码（4位）第一层第二层第三层0011110011置码十进制值=243+相应的属性代码值898001011100018962001011110019834001011010017819001111001116803001111001015787001111000114771001111000013706001010110012642001010100011578001010010010514001010000092570001100000824300110011117227001100111062110011001101519500110011004130001000100036600100001002200100000001十进制码二进制码叶结点号（2）基于四进制的线性四叉树编码对每个栅格进行编码得表a。检查相邻4个m码的属性值，如相同进行合并，除去最低值，。经过一次检测后，再检测上层相邻四个块编码的属性值，如相同再合并。循环到没有能合并的子块为止，得表b。首先将栅格阵列的行列值分别转换成二进制码，得二进制行号Ib,列号Jb，然后求出四进制四叉树码

MQ=2*Ib+Jb2）线性四叉树及编码333332323322233232223222111331330321320231230221220110313312303302213212203202101311310301300211210201200100133132123122033032023022011131130121120031030021020010113112103102013012003002001111110101100011010001000000111110101100011010001000列号行号表a333223223033023130130021200330320310300210100表b000000100属性值1101100100属性值21201033032031030020100四进制码191817161514131211叶结点号103393283173036302530143003232221四进制码叶结点号四进制的线性四叉树编码四进制线性四叉树编码的特点：优点是便于实现行列值及其编码之间的转换；缺点是存储开销大，且一般软件都不支持四进制。（2）基于四进制的线性四叉树编码2）线性四叉树及编码（3）基于十进制的线性四叉树编码编码：将二进制的行列号按位交错排列，可得到四叉树叶结点的二进制地址码，进而将二进制码转成十进制码，得到四叉树编码。001110行号=011010=列号MD=142）线性四叉树及编码表a经自下而上归并得表b。依次检查表a中四个相邻叶结点的属性代码是否相同。若相同则归并成一个父结点，记下地址及代码。否则不予归并。然后再归并更高一层父结点，如此循环，直到不能归并为止。（3)基于十进制的线性四叉树编码2）线性四叉树及编码636259584746434211161605756454441401105554515039383534101535249483736333210031302726151411100112928252413129801023221918763200121201716541000011111010110001101000100060564440515052494836321514131281640表a表b060056052051050049148044040136132016115114013012180400属性值MD码值属性值MD码值0491480401320161140121800四叉树游程编码特点：比四进制节省储存空间，且前后两个MD码之间差代表了叶结点的大小，还可进一步利用游程编码对数据进行压缩。优点：具有可变分辨率，能精确表示图形的细节部分，编码效率高；具有区域性质，适合于图形图像的分析运算；便于岛的分析。(3)基于十进制的线性四叉树编码2）线性四叉树及编码（三）四叉树优缺点优点：1）对于团块图像，四叉树表示法占用空间比网络法要少得多，四叉树表示法基本上是一种非冗余表示法。2）四叉树具有可变率或多重分辩率的特点使得它有很好的应用前景，适用于处理凝聚性或呈块状分布的空间数据，特别适用于处理分布不均匀的块状空间数据，但不适用于连续表面（如地形）或线状地物。此外，目前应用四叉树还存下列问题：1)矢/栅正反变换还不理想。2)

建立四叉树耗费机时很多。3)

四叉树虽可修改，但很费事（具体的数据结构中会提到）（三）四叉树优缺点4)

四叉树未能直接表示物体间的拓扑关系。5)

与非树表示法比较，四叉树表示法的缺点在于转换的不稳定性或叫滑动变异例如，两个图像的差异仅由于平移，就会构成极为不同的四叉树，因而很难根据四叉树来判断这两个图像是否全同，故不利于做形状分析和模式识别，

A0A1A4A5A2

B3B6B7A8A9B12B13A10A11B14B15AAAAABBBAABBAABB6)一个物体的图像在构成四叉树时会被分割到若干个象限中，使它失去了内在的相关性。AAAAABBBAABBAABB二、矢量数据结构-概念（一）概念矢量结构是表达空间数据的另一种常见数据结构，通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体。二、矢量数据结构-（二）基本特征点无大小、地理空间连续。

属性特征隐性表示。几何位置、属性数据、拓扑关系分别存储。指向地物、感觉宏观

几何实体无论大小，每个实体均匀一条数据记录存储，一条记录指向一个地物。二、矢量数据结构-（三）编码内容唯一标识符空间位置：（x,y）坐标对拓扑关系

属性特征时间特征

二、矢量数据结构-（三）编码内容（3.1）点实体编码内容点实体包括单独一对（x,y）坐标定位的一切地理或制图实体。点是空间上不能再分的地理实体，可以是具体的或抽象的。

二、矢量数据结构-（三）编码内容（3.1）点实体二、矢量数据结构-（三）编码内容（3.2）线实体由直线元素构成的各种线性要素。线实体主要用来表示线状地物符号线和多边形边界，有时也称为“弧”、“链”、“串”等。

线实体编码基本内容二、矢量数据结构-（三）编码内容（3.3）多边形区域实体中，具有名称属性和分类属性，多用多边形表示

。多边形矢量编码不但要表示位置和属性，更为重要的是要能表达区域的拓扑性质。

二、矢量数据结构-（四）矢量数据结构编码编码方法：无拓扑关系的编码方法：仅记录空间目标的位置和属性信息，而不记录拓扑关系。拓扑关系的编码方法：不仅记录空间目标的位置和属性信息，而且记录拓扑关系。二、矢量数据结构-（四）矢量数据结构编码（4.1）坐标序列法以多边形为单元进行组织。由多边形边界的x,y坐标对集合组成。边界坐标数据与多边形单元实体一一对应，各个多边形的边界都有单独编码和数字化。二、矢量数据结构-（四）矢量数据结构编码（4.1）坐标序列法10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；二、矢量数据结构-（四）矢量数据结构编码（4.1）坐标序列法

优点：编码容易、数字化操作简单、数据编排直观。缺点：多边形之间公共边界数字化两遍，数据冗余存储，多边形边界容易出现间隙或重叠。缺少的多边形的邻域信息和图形的拓扑关系。岛作为一个单独的图形，没有建立与外界多边形的联系。二、矢量数据结构-（四）矢量数据结构编码（4.2）树状索引结构编码采用树状索引，以减少数据冗余并间接增加邻域信息。具体方法：对所有边界点进行数字化，将坐标对以顺序方式存储，由点索引与边界号相联系，以线索引与各多边形相联系，形成树状索引结构。二、矢量数据结构-（四）矢量数据结构编码（4.2）树状索引结构编码数据记录形式：多边形文件多边形与线索引文件线文件边界线与点索引文件点文件点文件：点号—x,y坐标线文件：线号—起点—终点—点号序列多边形文件：多边形号—边界线号序列例：P148-P149索引式

BCDEabcfghefibcij12345678910111213141516171819202122232425262728293031线与多边形之间的树状索引

点与边界线之间的树状索引

二、矢量数据结构-（四）矢量数据结构编码（4.2）树状索引结构编码

优点：数据冗余小、编排直观、邻域信息和岛状信息可以得到一定处理。缺点：运算繁琐。邻接与包含关系处理困难。编码表要人工建立，工作量大、易出错。二、矢量数据结构-（四）矢量数据结构编码（4.3）双重独立结构编码（DIME）采用拓扑编码结构，以线文件为编码主体。数据记录形式：点文件：点号—x,y坐标线文件：线号—起点—终点—左多边形号—右多边形号特点：

数据冗余进一步缩小，数据检核、更新和检索方便，能自动生产多边形文件。

二、矢量数据结构-（四）矢量数据结构编码（4.3）双重独立结构编码11k12345678910abcdefhijlgⅠⅡⅢ线号左多边形右多边形起点终点aⅠⅡ12bⅠⅡ23cⅠⅡ34….…………k0Ⅰ1011l0Ⅰ114线文件二、矢量数据结构-（四）矢量数据结构编码（4.4）链状双重独立结构是对DIME方法的一种改进。DIME中一条边只能由直线两端点及相邻面域表示，而这种方法可以将若干线段合为一个弧段，每个弧段有许多中间点，其端点则为弧段的交点或起始点。二、矢量数据结构-（四）矢量数据结构编码（4.4）链状双重独立结构弧段坐标文件：一系列点的位置坐标组成。弧段文件：弧记录组成（记录弧的起止点号和左右多边形号）。多边形文件：多边形记录组成（多边形号、有关弧段号，周长、面积、中心点坐标、岛状区域信息）。二、矢量数据结构-（四）矢量数据结构编码线号坐标AX1,y1;X2,y2;X3,y3;X4,y4BX1,y1;X10,y10;X11,y11;X4,y4CX4,y4;X8,y8;X9,y9;X1,y1DX5,y5;X6,y6;X7,y7;X5,y5线号起点终点左多边形右多边形A14ⅠⅡB140ⅠC410ⅡD55ⅡⅢC11k12345678910abcdefhijlgⅠⅡⅢABD多边形号弧段号起始结点周长面积中心点坐标ⅠA，B1ⅡA，C，D1ⅢD5弧段坐标文件弧段文件多边形文件三、栅格-矢量数据一体化结构-比较矢量栅格基本特征点的认识点无大小点有大小地图空间连续离散数据指向地物位置属性显示隐式显式使用效果数据结构复杂简单数据量小大数据精度高低输出效果优劣（3.1）两种数据结构的比较三、栅格-矢量数据一体化结构-比较矢量栅格数据操作几何变形易难投影变换易难网络分析易难数据融合难易数学分析难易叠加分析难易应用范围数据采集、存储数据运算、分析三、栅格-矢量数据一体化结构-互换（3.2）两种数据结构的互换一、点的转换矢量结构：（X,Y）坐标精度的变化栅格结构：（行，列）

二、线的转换矢量结构点的内插栅格结构：数据精度降低栅格结构点的压缩矢量结构：坐标精度提高

三、面的转换矢量结构栅格结构：多边形填充栅格结构矢量结构：矢量化

（3.2）两种数据结构的互换-矢量向栅格转换矢量数据的坐标是直角坐标，原点为图的左下方；栅格数据的坐标是行列坐标，原点在图的左上方。在进行两种坐标数据转换时，通常使直角坐标的x，y轴分别同栅格数据的行、列平行。

（3.2）两种数据结构的互换-矢量向栅格转换①确定栅格单元的大小矢量数据向栅格数据转换时，首先必须确定栅格元素的大小，即分辨率。根据原矢量图的大小，精度要求、所研究问题的性质和存储空间，确定栅格的分辨率。

（3.2）两种数据结构的互换-矢量向栅格转换（3.2）两种数据结构的互换-矢量向栅格转换②点的转换

点的转换实质上是将点的矢量坐标转换成栅格数据中行列值i和j，从而得到点所在栅格元素的位置。

坐标精度的变化（3.2）两种数据结构的互换-矢量向栅格转换③线的转换

曲线可用折线来表示的，也就是当折线上取点足够多时，所画的折线在视觉上成为曲线。因此，线的变换实质上是完成相邻两点之间直线的转换。其转换过程不仅包括坐标点A，B分别从点矢量数据转换成栅格数据，还包括求出直线AB所经过的中间栅格数据。（3.2）两种数据结构的互换-矢量向栅格转换③线的转换具体转换过程：利用上述点转换法，将点A(x1，y1)，B(x2，y2)分别转换成栅格数据，求出相应的栅格的行、列值。由上述行列值求出直线所在行列值的范围。确定直线经过的中间栅格列值。

（3.2）两种数据结构的互换-矢量向栅格转换③线的转换

1)求出相应i行中心处同直线相交的y值。

2)用直线方程求出对应y值的点的x值。

3)从x，y值按公式求出相应i行的列值j。

YX（0,0）（3.2）两种数据结构的互换-矢量向栅格转换③线的转换

依据上述过程，依次求出直线经过的每个网格单元，并用直线的属性值去填充这些网格，就完成了线的转换。整个曲线或多边形边界经分段连续运算即可以完成转换。于此类似，可以先计算出两个端点的列值，知道直线要经过的列，然后计算各列中心线的Y值，再求出相应的行数I。（3.2）两种数据结构的互换-矢量向栅格转换④面的填充矢量数据结构中面域用边界线表示，面域内部是空心的；栅格数据结构中整个面域都要用属性值填充，因此，边界线转换完以后，必须进行面域属性值的填充。常用算法：1.内部点扩散算法2.复数积分算法3.射线法4.扫描算法5.边界代数算法（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—内部点扩散算法该算法由每个多边形一个内部点（种子点）开始，向其八个方向的邻点扩散，判断各个新加入点是否在多边形边界上，如果是边界上，则该新加入点不作为种子点，否则把非边界点的邻点作为新的种子点与原有种子点一起进行新的扩散运算，并将该种子点赋以该多边形的编号。

（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—复数积分算法对全部栅格阵列逐个栅格单元地判断该栅格归属的多边形编码，判别方法是由待判点对每个多边形的封闭边界计算复数积分，对某个多边形，如果积分值为2

i，则该待判点属于此多边形，赋以多边形编号，否则在此多边形外部，不属于该多边形。

（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—射线算法射线算法可逐点判断数据栅格点在某多边形之外或在多边形内，由待判点向图外某点引射线，判断该射线与某多边形所有边界相交的总次数，如相交偶数次，则待判点在该多边形外部，如为奇数次，则待判点在该多边形内部

采用射线算法，要注意的是：射线与多边形边界相交时，有一些特殊情况会影响交点的个数，必须予以排除。

射线算法射线算法的特殊情况（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—扫描算法扫描算法是射线算法的改进，将射线改为沿栅格阵列,列或行方向扫描线，常用的方法有：平行线扫描法和铅垂线跌落法。

（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—扫描算法

平行线扫描法：从待检验的栅格单元作一平行于x轴的扫描线，当与多边形相交的点数为偶数时，则该栅格在多边形之外，当交点为奇数时，该栅格在多边形之内。有时也会出现极值点的情况，就会出现错误判断。PQRabcdgfeYX（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—扫描算法

铅垂线跌落法：从待检验的栅格单元作一垂直于x轴的直线，检查它与多边形边界交点的点数，偶数时在多边形之外，奇数时在多边形之内。为了避免错误可同时采用这两种算法，只要一种方法交点为奇数，该点就在多边形之内。PQRabcdgfeYX（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—边界代数算法[任伏虎]⑴单个多边形初始化栅格阵列，所有单元赋值为0。欲填充多边形值为a。以栅格行列为参考坐标轴，以多边形边界上某一点为起始点顺时针方向搜索边界。边界上行时，左侧同行栅格单元值-a。边界下行时，左侧同行栅格单元值+a。回到起点，形成栅格多边形。（3.2）两种数据结构的互换-矢量向栅格转换（3.2）两种数据结构的互换-矢量向栅格转换④面的填充—边界代数算法⑵多个多边形对每幅地图的全部具有左右多边形编号的边界弧段,沿其前进的方向逐个搜索,当边界上行时,将边界线位置与左图框之间的网格点加上一个值=(左多边形编号-右多边形编号);当边界下行时,将边界线位置与左图框之间的网格点加上一个值=(右多边形编号-左多边形编号);当边界平行栅格行行走时,不做运算。（3.2）两种