| 空间叠加分析中的分而治之算法研究与应用 |
| |
| 引用本文： | 李峙,陈朝晖.空间叠加分析中的分而治之算法研究与应用[J].计算机工程与应用,2009,45(34):230-232. |
| |
| 作者姓名： | 李峙 陈朝晖 |
| |
| 作者单位： | 1.中国科学院 广州地球化学研究所，广州 510640 2.中国科学院 研究生院，北京 100039 3.广西师范学院 资源与环境科学学院，南宁 530001 4.南宁市国土资源信息中心，南宁 530022 |
| |
| 摘 要： | 土地利用现状数据由CAD格式转换为GIS格式后需重新为图斑对象设置土地分类编码属性，为了提高海量空间数据情况下自动赋值的效率，研究了将分而治之算法应用于海量数据空间叠加分析以提高效率的方法。研究表明，对于所有需通过空间叠加分析来确定不同图层空间对象间的空间关系的问题，均可以采用分而治之方法来降低时间复杂度。在最小化分割的情况下，基于四叉树空间索引，分而治之算法可以使此类应用的时间复杂度降低为O（n lb n）。实际应用验证了该方法在海量空间数据处理中的效率和实用价值。
|
| 关 键 词： | 分而治之 空间叠加分析 四叉树 数据转换 地理信息系统(GIS) |
| 收稿时间： | 2009-4-20 |
| 修稿时间： | 2009-6-2
|
Study and Applications of divide and conquer algorithm in spatial overlay analysis |
| |
| LI Zhi,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. |
| |
| Authors: | LI Zhi CHEN Chao-hui |
| |
| Affiliation: | 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 |
| |
| 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. |
| |
| Keywords: | divide and conquer spatial overlay analysis quadtree data transformation Geographic Information System(GIS) |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
