第25卷�第3期2009年5月地理与地理信息科学GeographyandGeo-InformationScienceVol.25�No.3May2009��收稿日期:2008-12-09;�修订日期:2009-01-05��基金项目:国家基础科学人才培养基金(J0630535)��作者简介:沈定涛(1983-),男,硕士研究生,主要研究方向为地理信息系统。E-mail:sdt2003@163.com一种顾及属性的游程编码�交运算方法与实验沈定涛,王结臣,陈焱明,于�庆(南京大学地理信息科学系,江苏南京210093)摘要:考虑到基于直接编码的栅格数据在计算效率和存储能力上的不足,提出一种便于代数操作的游程编码数据结构,以优化基于直接编码栅格数据的代数运算。介绍了基于该数据结构的游程�交运算的实现方法,并在算法实现过程中完成游程属性的各种代数运算。算法实现思路为:将栅格场中任一行游程集合以链表的形式存储,将欲执行代数运算的新游程单元与对应栅格行游程集合执行游程�交运算,并在插入删除游程结点的过程中完成属性值的代数运算。该算法通用性较强,在数据精度及计算效率方面比直接栅格编码方法具有优势。关键词:游程编码;栅格数据;�交运算中图分类号:P208��文献标识码:A��文章编号:1672-0504(2009)03-0008-04��游程编码是一种重要的栅格数据压缩方法,广泛应用于GIS空间数据的压缩存储。现有的游程编码方法研究一般侧重于栅格数据的压缩、编码及解码等策略的实现与优化[1-3],基于游程编码数据结构的栅格运算则研究较少。基于栅格数据的运算主要是针对栅格单元的属性进行各种代数运算和逻辑运算,其运算过程简便,而游程编码既能高效的压缩栅格数据,又能保持栅格数据比较直观的优点。因此,若将二者有效地结合,在GIS空间分析中采用基于游程的运算,将兼具内存占用低、运算效率高的优点。基于游程的�交运算是栅格代数运算中重要的运算方法之一,本文着重研究便于代数操作的游程编码数据结构以及�交运算的实现方法。最后,以�交运算在多边形叠置分析中的应用为例,表明游程的�交运算应用于相关空间分析算法设计中,能有效地简化算法复杂性、提高算法效率。1�游程编码数据结构栅格数据结构是指将空间分割成规则的网格,在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式[4]。栅格数据显式地表达了各栅格单元的属性值信息,任一栅格单元的行列号则隐式地表达了该栅格单元的坐标信息。游程编码方法是逐行将相邻同值的网格合并,并记录合并后网格的值以及合并网格的长度,以此压缩栅格数据,消除数据间的冗余。常规的游程编码方法以一个二维数组表示游程,每个游程单元以一对数值表达,第一个值表示游程的属性,第二个值表示游程的长度[5],一行上每个游程的长度相加就等于该栅格场的列数。这种数据结构比较直观,能够有效的压缩栅格,解码也很容易,但在进行其他操作时相当不便。对于某游程单元,为了确定它的左右端点(该游程单元的起始列和终止列)在该行栅格中的位置,必须遍历该游程前所有游程,统计各游程的长度。王结臣等[6]提出通过链表的方式存储游程单元,该游程单元不直接存储游程的长度,而是存储游程左右端点所在的列号以及指向下一游程的指针。通过一个行游程结构体将每行的游程串联起来,这样由每行的起点游程即可访问此行任一游程单元。在某栅格行上,只有地理实体跨过的栅格单元才会用游程表示,因此游程单元之间允许有�空隙存在。但在该研究中,游程不带属性值,仅适于执行游程的合并运算,无法应用于更广泛的游程代数运算。考虑到很多GIS数据都带有属性信息,在很多空间分析算法中属性值也是一个重要的参照要素,因此,本文为每个游程单元加上属性信息。在算法实现过程中,并不是为每个游程单元显式地记录该属性值,而是为整个待处理数据建立一个属性值列表,并为各游程单元建立属性值索引,将游程单元与属性表对应的属性值联系起来,通过游程单元所在的属性表索引即可找到该游程对应的属性值。因此,本文设计了一种新的游程编码数据结构,用C语言描述如下:structRun�Length_Node//游程结点{�intStart,End;//游程起始列号、终止列号�Run�Length_Node*next;//下一游程地址指针�intAttributeIndex;//属性表索引};structRun�Length_LINE//行游程链表{�intNode_Num;//该行...
