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

doi:10.3778/j.issn.1002-8331.2009.34.072

计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (34): 230-232.DOI: 10.3778/j.issn.1002-8331.2009.34.072

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

李峙^1，2，3，陈朝晖⁴

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

收稿日期:2009-04-20 修回日期:2009-06-02 出版日期:2009-12-01 发布日期:2009-12-01
通讯作者: 李峙

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

LI Zhi^1，2，3，CHEN Chao-hui⁴

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

摘要/Abstract

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

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 O（n 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.

中图分类号:

TP301.6

李峙^1，2，3，陈朝晖⁴. 空间叠加分析中的分而治之算法研究与应用[J]. 计算机工程与应用, 2009, 45(34): 230-232.

LI Zhi^1，2，3，CHEN Chao-hui⁴. Study and Applications of divide and conquer algorithm in spatial overlay analysis[J]. Computer Engineering and Applications, 2009, 45(34): 230-232.

[1]	李冬梅^1，2，林友芳²，黄厚宽². 基于E_DAG的本体不一致性诊断算法研究[J]. 计算机工程与应用, 2010, 46(9): 19-22.
[2]	牛昱光，阎高伟，谢刚，谢克明. 基于粒计算的多目标排序方法研究[J]. 计算机工程与应用, 2010, 46(9): 42-45.
[3]	王训斌，陆慧娟，张火明. 物流动态车辆调度问题的混合禁忌搜索算法[J]. 计算机工程与应用, 2010, 46(8): 228-231.
[4]	肖拥军，李铁克，尹兆涛. 考虑特殊时间约束的混合流水车间调度[J]. 计算机工程与应用, 2010, 46(8): 205-207.
[5]	任小康，孙正兴，郝瑞芝. 粗糙集的模糊性度量与SVM的混合分类算法[J]. 计算机工程与应用, 2010, 46(7): 46-48.
[6]	谢安世¹，周传华^1，2，徐新卫¹，张芬¹. 基于PK模型的一种自适应遗传算法研究[J]. 计算机工程与应用, 2010, 46(7): 52-56.
[7]	袁浩，何波，李敏. 基于时空混沌的S盒产生算法[J]. 计算机工程与应用, 2010, 46(7): 115-117.
[8]	罗义钦^1，2，倪志伟^1，2，杨葛钟啸^1，2. 一种新的数据流分形聚类算法[J]. 计算机工程与应用, 2010, 46(6): 136-138.
[9]	钱文彬¹，徐章艳¹，黄丽宇¹，杨炳儒². 基于信息熵的二进制差别矩阵属性约简算法[J]. 计算机工程与应用, 2010, 46(6): 120-123.
[10]	柴秀荣^1，2，王儒敬¹. 多出救点、多物资应急调度算法研究[J]. 计算机工程与应用, 2010, 46(6): 224-226.
[11]	王芳，戴永寿，王少水. 改进的混沌遗传算法[J]. 计算机工程与应用, 2010, 46(6): 29-32.
[12]	王轩，肖莉，林艳娥. 一种求解旅行商问题的热力学演化算法[J]. 计算机工程与应用, 2010, 46(5): 48-50.
[13]	杨家稳^1，2，孙合明¹，钟青¹，胡珊珊¹. 多维联想记忆神经网络在图像回忆中的应用[J]. 计算机工程与应用, 2010, 46(4): 186-188.
[14]	康燕¹，冯海朋²，须文波³，杨燕萍¹. 合作的具有量子行为粒子群优化算法[J]. 计算机工程与应用, 2010, 46(4): 39-42.
[15]	栗青生¹，杨玉星¹，马季兰². 基于粘贴模型的两类全排问题的DNA算法[J]. 计算机工程与应用, 2010, 46(4): 46-48.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics