Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (34): 230-232.DOI: 10.3778/j.issn.1002-8331.2009.34.072

• 工程与应用 • Previous Articles     Next Articles

Study and Applications of divide and conquer algorithm in spatial overlay analysis

LI Zhi1,2,3,CHEN Chao-hui4   

  1. 1.Guangzhou Institute of Geochemistry,Chinese Academy of Sciences,Guangzhou 510640,China
    2.Graduate University of Chinese Academy of Sciences,Beijing 100039,China
    3.School of Resources and Environmental Sciences,Guangxi Teachers Education University,Nanning 530001,China
    4.Information Center of Land and Resources of Nanning,Nanning 530022,China
  • Received:2009-04-20 Revised:2009-06-02 Online:2009-12-01 Published:2009-12-01
  • Contact: LI Zhi

空间叠加分析中的分而治之算法研究与应用

李 峙1,2,3,陈朝晖4   

  1. 1.中国科学院 广州地球化学研究所,广州 510640
    2.中国科学院 研究生院,北京 100039
    3.广西师范学院 资源与环境科学学院,南宁 530001
    4.南宁市国土资源信息中心,南宁 530022
  • 通讯作者: 李 峙

Abstract: To improve the efficiency of assigning the land codes to the massive spatial objects automatically after the land-use data are transformed from CAD format into GIS format,the methods using a divide and conquer algorithm to improve the efficiency of the spatial overlay analysis in massive spatial data are studied.The research shows that a divide and conquer algorithm can help decreasing the time complexity of solving any problems that need to determine the spatial relationships of spatial objects distributed in different map layers.Based on a quadtree spatial index,the divide and conquer algorithm can decrease the time complexity to On lb n) in these applications by minimized divisions.The efficiency of handling massive spatial data by this method and its powerful practical merits are verified in applications.

摘要: 土地利用现状数据由CAD格式转换为GIS格式后需重新为图斑对象设置土地分类编码属性,为了提高海量空间数据情况下自动赋值的效率,研究了将分而治之算法应用于海量数据空间叠加分析以提高效率的方法。研究表明,对于所有需通过空间叠加分析来确定不同图层空间对象间的空间关系的问题,均可以采用分而治之方法来降低时间复杂度。在最小化分割的情况下,基于四叉树空间索引,分而治之算法可以使此类应用的时间复杂度降低为On lb n)。实际应用验证了该方法在海量空间数据处理中的效率和实用价值。

CLC Number: