一种道路网信息几何差异检测算法  

An Algorithm for Detecting the Geometric Difference between the Road Networks

作　　者：张韵 李清泉[2] 曹晓航 徐晋晖 

机构地区：[1]北京四维图新科技股份有限公司,北京100088 [2]武汉大学交通研究中心,湖北武汉430072

出　　处：《测绘学报》2008年第4期521-525,共5页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金项目(40571134);国家973计划项目(2006CB705500)

摘　　要：道路网信息几何差异的检测在导航电子地图数据更新,数据压缩和质量检查中具有重要的现实意义。针对道路网信息和道路信息几何差异检测的实际应用特点,对传统的平面扫描线算法进行改进,提出一种新的计算道路网信息几何差异的高效算法。该方法的计算复杂度为O((n+s)logn),n表示输入数据大小,s表示线段交点的个数;并且在实际地图生产中得到应用,结果表明该算法效率高,符合应用需求,可靠性好。Detecting the geometric difference between the road networks has a realistic significance on the data update, data compression and quality check in navigation map . Considering the feature of the problem in ques tion, we propose an algorithm based on sweep line paradigm that can find the geometric difference between the road networks efficiently. Its computational complexity is O（（n＋s）logn）,where n is the input data size and s is the intersections. The practical application has demonstrate that the proposed algorithm achieves a good per formance in terms of efficiency and robustness,which meets the requirement.

关 键 词：扫描线算法 道路网 几何差异 几何变化检测 

分 类 号：P208[天文地球—地图制图学与地理信息工程]