矢量地图叠加分析算法研究_朱效民.docx

第 15 卷 第 11 期2010 年 11 月中国图象图形学报Journal of Image and GraphicsVol． 15，No． 11 Nov． ，2010中图法分类号: TP301． 6文献标志码: A文章编号: 1006-8961( 2010) 11-1696-11检索信息: 朱效民，赵红超，刘 焱，廖 浩 均，方 金 云，韩 承 德． 矢 量 地 图 叠 加 分 析 算 法 研 究［J］． 中 国 图 象 图 形 学 报，2010，15( 11) : 1696-1706矢量地图叠加分析算法研究朱效民1) ，2) ，赵红超1) ，刘焱1) ，2) ，廖浩均1) ，2) ，方金云1) ，韩承德1)1) ( 中国科学院计算技术研究所，北京 100190)2) ( 中国科学院研究生院，北京 100049)摘 要: 提出了一整套矢量地图叠加分析算法: 提出了大量点与多边形关系的包含性测试方法，首先对多边形进行 预处理，然后采用射线法对单个点进行包含性测试; 提出了基于双索引的大量线裁剪方法，分别以线、线段为基础 建立两层索引，有效去除不必要的求交运算; 面面叠加，基于改进的扫描线方法求取交点; 通过对过同一点的线段 分布情形的完备分类，涵盖了所有特殊类型的交点; 在构造环的过程中，保存整型 ID 信息，并利用 ID 完成内环外 环的匹配以及属性继承。以上几何计算方法及对应的叠加分析功能都已经实现，与必威体育精装版研究成果的对比以及与 ArcGIS 对应功能的对比，都证明了其正确鲁棒、高效可用。上述实现已经应用于实际的 GIS 系统中，取得了良好的效果。 关键词: 地理信息系统; 空间分析; 叠加分析; 矢量地图叠加; 点的包含性测试; 线裁剪Research on vector map overlayZhu Xiaomin1) ，2) ，Zhao Hongchao1) ，Liu Yan1) ，2) ，Liao Haojun1) ，2) ，Fang Jinyun1) ，Han Chengde1)1) ( Institute of Computing Technology，Chinese Academy of Sciences，Beijing 100190)2) ( Graduate University of Chinese Academy of Sciences，Beijing 100049)Abstract: In this paper，we introduce a series of algorithms for vector map overlay: We proposed an algorithm for large amounts of points inclusion test，which first preprocesses the polygon and then adopts the ray-crossing idea for each point inclusion test． We proposed an algorithm for large amounts of lines clipping，which builds indexes on the whole line and the segment，and avoids unnecessary intersection-computing． For map overlay on polygons，we use the improved plane sweep algorithm to get all the intersection points，and the complete categories on distribution of segments passing the same point cover all the special cases of intersection points． We record the ID in the process of constructing the result rings，which simplifies the two processes-finding outer ring for holes and attribute propagation． All the geometric algorithms and the corresponding overlay functions are implemented，and the comparisons with the state-of-the-art algorithms and ArcGIS’s func