一种地图线要素综合化简递归并行算法  

A parallel algorithm to generalize and simplify linear map features

作　　者：徐国庆 赵明瑜[2] 杨苗苗 李晓明 XU Guoqing;ZHAO Mingyu;YANG Miaomiao;LI Xiaoming(Technical Division of Surveying and Mapping,Xi'an 710054,China;Xi'an Research Institute of Surveying and Mapping,Xfan 710054,China)

机构地区：[1]测绘信息技术总站,陕西西安710054 [2]西安测绘研究所,陕西西安710054

出　　处：《测绘科学与工程》2019年第4期63-68,共6页Geomatics Science and Engineering

摘　　要：移动地图和网络地图等电子地图的服务为人们出行带来了很多便利,它要求电子地图服务商具有快速处理地图的能力(如更新、综合等),地图综合是地图快速处理中一个非常重要的坏节,如何实现快速自动处理,巳成为目前研究的热点。Li-Openshaw算法是一种以人的视觉特点为基础的自适应线状要素综合算法,使用该算法可得到比较合理、真实的综合结果。针对Li-Openshaw算法计算量大、串行处理效率不高的问題,本文在分析Li-Openshaw要素综合算法的基础上,利用Fork-Join计算模型对线要素进行递归二分分割,实现了并行Li-Openshaw要素综合算法,并在多核处理器上进行了实验。结果表明:该算法相校于按数据集分割的并行Li-Openshaw算法在时间消耗上有一定的改进,并且随着处理器核心数(原生践程数)的增加,算法性能会进一步提高;但该算法模型在创建线程、销毀线程、线程间的通信以及上下文切换的计算过程中均有一定的时间损耗。因此,本文的算法在各线要素相对较长时具有比较好的处理性能。Electronic map services,such as the mobile and internet map,have brought a lot of convenience for travelling,which requires the service providers have the ability to quickly update or generalize maps.Map generalization is an important step for rapid map processing,and how to realize the rapid automatic processing has become a research hotspot.Li-Openshaw is a type of self-adaptive linear feature generalization and simplification algorithm based on human visual characteristics,which can achieve more rea^jonable real map generalization results.Since tlie Liopenshaw algorithm features large amount of calculation and low efficiency in serial processing,the Fork-Joi n computing model is used to carry out a recursive dichotomy segmentation of line elements based on an analysis of Li-Openshaw line element synthesis algorithm,and the parallel Li-openshaw line element synthesis algorithm is realized.Experiments are carried out on a multi-core processor.Tlie results show that this algorithm reduces the processing time to some extent comparerl with the parallel Li-openshaw algorithm which conduct segmenlalion by data set,and the algorithm performance will the further improved with the increase of processor cores(native threads).However,this algorithm model will cause certain time loss in the process of calculation,such as thread creation,thread destruction,and communication between threads and context switch.Therefore,the algorithm proposed in this paper can actually provide better processing performance when the elements of each line are relatively long.

关 键 词：地图综合 Li-Openshaw 算法 并行计算 多核处理器 Fork-Join模型 

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