Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (25): 41-44.DOI: 10.3778/j.issn.1002-8331.2009.25.013

• 研究、探讨 • Previous Articles     Next Articles

Polygon overlay operation using run-length encoding

SHEN Ding-tao,WANG Jie-chen,CUI Can   

  1. Geographic Information Science Department,Nanjing University,Nanjing 210093,China
  • Received:2008-10-23 Revised:2008-12-26 Online:2009-09-01 Published:2009-09-01
  • Contact: SHEN Ding-tao

借助游程运算实现多边形叠置分析

沈定涛,王结臣,崔 璨   

  1. 南京大学 地理信息科学系,南京 210093
  • 通讯作者: 沈定涛

Abstract: Aiming at the low computation efficiency and storage insufficiency of direct-encoded raster data,a new data structure on the basis of run-length encoding has been proposed to optimize the algebraic operations.The realization of “intersection” is introduced;moreover,all kinds of algebraic operations on the run-length’s attribute are performed during the realization process.Adopting this“intersection” operation to implement polygon overlay,the steps are as follows:firstly,convert the polygons on two different layers into run-length sets,and then intersect the run-length set of the base layer with the run-lengths of the adding layer;afterwards,extract the required run-length units according to different overlay modes;finally,vectiorize the run-lengths into polygons.

Key words: run-length encoding, raster data, overlay analysis

摘要: 考虑到基于直接编码的栅格数据在计算效率和存储能力上的不足,提出一种便于代数操作的游程编码数据结构,以优化基于直接编码栅格数据的代数运算。介绍了基于该数据结构的游程“交”运算的实现方法,并在算法实现过程中完成游程属性的各种代数运算。提出使用这种游程的“交”运算完成多边形的叠置分析,其基本思路是:分别将两个图层中的多边形数据转换为游程集合,在栅格场中的任一行上使用叠加图的游程单元与底图上该行的游程集合执行“交”运算,逐行执行这种游程“交”运算得到两个图层之间多边形相交的结果游程集合,并根据“Union”、“Erase”等不同的叠置方式提取满足条件的游程单元,最后将游程矢量化为多边形数据输出。在叠置运算过程中,通过游程的“交”运算即能够实现图层间多边形的各种叠置方式,表明该运算具有很强的通用性。

关键词: 游程编码, 栅格数据, 叠置分析

CLC Number: