基于R+树的地图叠加分析双重循环算法  

A Dual Loop Map Overlay Algorithm Based on R+ Tree

作　　者：董鹏[1] 杨崇俊[1] 刘冬林[1] 芮小平[1] 

机构地区：[1]中国科学院遥感应用研究所,北京100101

出　　处：《中国图象图形学报（A辑）》2003年第6期703-710,共8页Journal of Image and Graphics

基　　金：国家自然科学基金 ( 4 0 0 710 65 );国际科技合作重点项目 ( ANFAS)

摘　　要：地图叠加是非常重要的 GIS空间分析功能之一 ,为此 ,提出了一种新的基于 R+树空间索引的矢量地图叠加分析双重循环算法 ,首先采用多边形穷举求交方法计算出线段相交点 ;然后运用引入、引出交点交替配对的叠加结果弧线段生成原则 ,进一步实现了面面叠加和线面叠加的双重循环算法 ;最后引入 R+树空间索引对空间数据的高效存取机制 ,对算法进行改进 ,进一步提高了计算速度 .实践结果表明 ,该算法快速、有效 ,具有较强的应用价值 .Map Overlay is an important spatial analysis in Geographic Information Systems. This paper presents a novel dual loop algorithm based on R+tree to process vector map overlay analysis. The paper first figures out intersection points of line segments with enumerating method of polygon intersection, then uses the matching principle of 'import export intersection point' to form the result arcs and further realize the dual loop algorithm of polygon on polygon and line on polygon vector overlay analysis; finally, perfects the algorithm through an efficient spatial access method-R+tree index and it's efficient query and filter mechanism to spatial data, so excludes large amounts of unused graphics elements and advances the computational speed very much. This algorithm has been applied to the software development of the commercial geographic information systems. Performance tests confirm that the R+tree map overlay algorithm is quick and efficient, and has powerful practical merits.

关 键 词：地图叠加 GIS 双重循环算法 数据结构 拓扑结构 R+树 

分 类 号：P283[天文地球—地图制图学与地理信息工程] P208[天文地球—测绘科学与技术]