lecture2栅格数据结构详解

二、栅格数据结构

基于栅格模型的数据结构简称为栅格数据结构，是指将空间分割成有规则的网格，称为栅格单元（像元），在各个栅格单元上给出相应的属性值来表示地理实体的一种数据组织形式。lecture2栅格数据结构详解全文共28页，当前为第1页。

栅格数据模型是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地理要素的非几何属性特征。特点：属性明显，定位隐含。表示连续现象获取方法：

(1)手工网格法；

(2)扫描数字化法；

(3)分类影像输入法；

(4)数据结构转换法。8888888888888888888888888888888888888888888881111111111111122222222222322lecture2栅格数据结构详解全文共28页，当前为第2页。矢量结构栅格结构

lecture2栅格数据结构详解全文共28页，当前为第3页。1111222211112222111122231111333311333333113333334334333344444444行列单元属性值矩形（正方形）栅格单元lecture2栅格数据结构详解全文共28页，当前为第4页。空间分辨率：一个像元所代表的地面实际面积的大小。分辨率的确定：以保证最小多边形的精度来确定网格的尺寸。分辨率需要的像元（网格单元）100m10000个10m1000000个面积100km2的区域lecture2栅格数据结构详解全文共28页，当前为第5页。栅格单元的代码获取单位网格交点归属法（中心点法）：用处于栅格中心处的地物类型或现象特性决定栅格代码。在图所示的矩形区域中，中心点O落在代码为C的地物范围内，按中心点法的规则，该矩形区域相应的栅格单元代码应为C中心点法常用于具有连续分布特性的地理要素，如降雨量分布，人口密度图等。

lecture2栅格数据结构详解全文共28页，当前为第6页。面积占优法：以占矩形区域面积最大的地物类型或现象特性决定栅格单元的代码。在图中，显见B类地物所占面积最大，故相应栅格代码定为B。面积占优法常用于分类较细，地物类别斑块较小的情况。单位栅格长度占优法：当覆盖的格网过中心部位时，横线占据该网格中的大部分长度的属性值定为栅格单元的代码。重要性法：根据栅格内不同地物的重要性，选取最重要的地物类型决定相应的栅格单元代码、假设图中A类为最重要的地物类型，即A比B和C类更为重要，则栅格单元的代码应为A。重要性法常用于具有特殊意义而面积较小的地理要素，特别是点、线状地理要素，如城镇、交通枢钮、交通线、河流水系等，在棚格中代码应尽量表示这些重要地物。百分比法：根据矩形区域内各地理要素所占面积的百分比数确定栅格单元的代码参与，如可记面积最大的两类BA，也可根据B类和A类所占面积百分比数在代码中加入数字。栅格单元的代码获取lecture2栅格数据结构详解全文共28页，当前为第7页。栅格数据的编码方法栅格数据为什么要编码？常见的编码方法有哪些？1、直接栅格编码2、行程编码（变长编码）3、块码（游程编码向二维扩展）4、链式编码、Freeman链码、边界链码5、四叉树编码lecture2栅格数据结构详解全文共28页，当前为第8页。1逐个像元编码（完全栅格编码）

将栅格数据看作一个数据矩阵，逐行（或逐列）逐个记录代码，可以每行从左到右逐像元记录，也可奇数行从左到右而偶数行由右向左记录，为了特定的目的还可采用其他特殊的顺序。

02255555222225550000033322223355002333550033335300033333000033330，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。lecture2栅格数据结构详解全文共28页，当前为第9页。由起点位置和一系列在基本方向的单位矢量给出每个后续点相对其前继点的可能的8个基本方向之一表示。8个基本方向自0°开始按逆时针方向代码分别为0，1，2，3，4，5，6，7。单位矢量的长度默认为一个栅格单元。2、链码12345076001076701100lecture2栅格数据结构详解全文共28页，当前为第10页。链码编码：

2，2，6，7，6，0，6，5123450760500000000500000000000000500000000550000000500000050000000000000链码编码示例lecture2栅格数据结构详解全文共28页，当前为第11页。3、游程长度编码(1)只在各行（或列）数据的代码发生变化时依次记录该代码以及相同代码重复的个数；0225555522222555000003332222335500233355003333530003333300003333沿行方向进行编码：(0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。lecture2栅格数据结构详解全文共28页，当前为第12页。3、游程长度编码（2）逐个记录各行（或列）代码发生变化的位置和相应代码。0225555522222555000003332222335500233355003333530003333300003333沿列方向进行编码：(1，0），（2，2），（4，0）；（1，2），（4，0）；（1，2），（5，3），（6，0）；（1，5），（2，2），（4，3），（7，0）；（1，5），（2，2），（3，3），（8，0）；（1，5），（3，3）；（1，5），（6，3）；（1，5），（5，3）。lecture2栅格数据结构详解全文共28页，当前为第13页。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）。lecture2栅格数据结构详解全文共28页，当前为第14页。四叉树结构四叉树又称四元树或四分树，是最有效的栅格数据压缩编码方法之一。四分树将整个图像区域逐步分解为一系列方形区域，且每一个方形区域具有单一的属性。最小区域为一个象元。lecture2栅格数据结构详解全文共28页，当前为第15页。区域分割原则：将欲分解区域等分为四个象限，再根据各个象限的象元值是否单一决定要不要再分。如果单一则不再分割，否则同法再分，直到所有象限的象元属性值相同为止。lecture2栅格数据结构详解全文共28页，当前为第16页。四叉树数据结构分类常规四叉树除了记录叶结点之外，还要记录中间结点。结点之间借助指针联系，每个结点需要用六个量表达：四个叶结点指针，一个父结点指针和一个结点的属性或灰度值。这些指针不仅增加了数据贮存量，而且增加了操作的复杂性。常规四叉树主要在数据索引和图幅索引等方面应用。线性四叉树则只存贮最后叶结点的信息。包括叶结点的位置、深度和本结点的属性或灰度值。所谓深度是指处于四叉树的第几层上。由深度可推知子区的大小。线性四叉树叶结点的编号需要遵循一定的规则，这种编号称为地址码，它隐含了叶结点的位置和深度信息。最常用的地址码是四进制或十进制的Morton码。

四叉树数据结构lecture2栅格数据结构详解全文共28页，当前为第17页。00000000000000000000000000000100111111001111110011110000111100000000000111000612139101178145230000000000000010011100110000000000（a）（b）（c）（d）栅格矩阵数据第一次四叉分割结果第二、三次四叉分割结果四叉树节点编号lecture2栅格数据结构详解全文共28页，当前为第18页。12345678910111213根节点第1次分割第2次分割第3次分割（e）常规四叉树lecture2栅格数据结构详解全文共28页，当前为第19页。线性四叉树存储MortonSizeValue04×41242×21491×11（f）线性四叉树4243464758596263404144455657606134353839505154553233363748495253101114152627303189121324252829236718192223014516172021

莫顿码栅格顺序lecture2栅格数据结构详解全文共28页，当前为第20页。四叉树编码

是根据栅格数据二维空间分布的特点，将空间区域按照4个象限进行递归分割（2n×2n，且n>1），直到子象限的数值单调为止，最后得到一棵四分叉的倒向树。四叉树分解，各子象限大小不完全一样，但都是同代码栅格单元组成的子块，其中最上面的一个结点叫做根结点，它对应于整个图形。不能再分的结点称为叶子结点，可能落在不同的层上，该结点代表子象限单一的代码，所有叶子结点所代表的方形区域覆盖了整个图形。从上到下，从左到右为叶子结点编号，最下面的一排数字表示各子区的代码。为了保证四叉树分解能不断的进行下去，要求图形必须为2n×2n的栅格阵列。n为极限分割次数，n＋1是四叉树最大层数或最大高度lecture2栅格数据结构详解全文共28页，当前为第21页。0225555522222555000003332222335500233355003333530003333300003333①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南东南西北东北000…00001101001122位6位4位lecture2栅格数据结构详解全文共28页，当前为第22页。编码按位操作十进制行号：Rb=(rnrn-1…r3r2r1)十进制列号：Cb=(cncn-1…c3c2c1)Rb=(rnrn-1…r3r2r1)Cb=(cncn-1…c3c2c1)Mb=(rncnrn-1cn-1…r3c3r2c2r1c1)二进制转化为十进制lecture2栅格数据结构详解全文共28页，当前为第23页。举例:线性四叉树编码四进制编码为：MQ=2II+JJ=2*110+011=231二进制表示的十进制编码为：Mb=II2JJ2II1JJ1II0JJ0=101101十进制编码为：MD=25+23+22+1=45lecture2栅格数据结构详解全文共28页，当前为第24页。lecture2栅格数据结构详解全文共28页，当前为第25页。栅格编码方法总结AAAAARAAARAAARAARAAAAAAAAA