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

道路网信息几何差异的检测在导航电子地图数据更新,数据压缩和质量检查中具有重要的现实意义。针对道路网信息和道路信息几何差异检测的实际应用特点,对传统的平面扫描线算法进行改进,提出一种新的计算道路网信息几何差异的高效算法。该方法的计算复杂度为O((n s)logn),n表示输入数据大小,s表示线段交点的个数;并且在实际地图生产中得到应用,结果表明该算法效率高,符合应用需求,可靠性好。

An Algorithm for Detecting the Geometric Difference between the Road Networks

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 question,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 performance in terms of efficiency and robustness,which meets the requirement.