利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素

马劲松; 沈婕; 徐寿成

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素

马劲松, 沈婕, 徐寿成

文章导航 > 武汉大学学报 ● 信息科学版 > 2011 > 36(12): 1423-1426

马劲松, 沈婕, 徐寿成. 利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J]. 武汉大学学报 ● 信息科学版, 2011, 36(12): 1423-1426.

引用本文:

马劲松, 沈婕, 徐寿成. 利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J]. 武汉大学学报 ● 信息科学版, 2011, 36(12): 1423-1426.

MA Jinsong, SHEN Jie, XU Shoucheng. A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers[J]. Geomatics and Information Science of Wuhan University, 2011, 36(12): 1423-1426.

Citation:

MA Jinsong, SHEN Jie, XU Shoucheng. A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers[J]. Geomatics and Information Science of Wuhan University, 2011, 36(12): 1423-1426.

利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素

¹南京大学地理信息科学系,南京市汉口路22号210093;²南京师范大学地理科学学院,南京市文苑路1号210046;³南京师范大学虚拟地理环境教育部重点实验室,南京市文苑路1号210046

基金项目: 国家自然科学基金资助项目(41071288)

详细信息

作者简介:
马劲松，副教授，博士，主要从事地图学和３ＤＧＩＳ的教学与研究。目前已经发表学术论文６０多篇。

中图分类号: P283.1;P208

A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers

¹ Department of Geographic Information Science,Nanjing University,22 Hankou Road,Nanjing 210093,China;² Institute of Geographic Science,Nanjing Normal University,1 Wenyuan Road,Nanjing 210046,China;³Key Laboratory of Virtual Geographic Environment of Ministry of Education,Nanjing Normal University, 1 Wenyuan Road,Nanjing 210046,China

Funds: 国家自然科学基金资助项目(41071288)

摘要: Douglas-Peucker算法是线要素简化的经典算法,针对其存在大量计算、难以做到实时的缺点,运用并行技术实现Douglas-Peucker算法,并在多核处理器的计算机上进行实验,验证了并行算法的效率与实时性。
- 地图综合 /
- Douglas-Peucker算法 /
- 并行算法 /
- 多核处理器 /
- 串行算法
Abstract: The Douglas-Peucker polyline simplification algorithm has been widely adopted in map generalization for decades,though it is often criticized for its low performance.As multi-core processor computers become widely available,it might be a good opportunity to improve the performance by converting its sequential implementation to parallel form.We present three different parallel implementations of the Douglas-Peucker algorithm.The first is in either recursive or non-recursive manner using OpenMP.The second is done by splitting a polyline feature into irrelevant segments and distributing segments to parallel threads.The third method is to dispatch each polyline feature to an idle parallel thread in which the conventional sequential method is applied.By utilizing the official China's provincial boundary geospatial data set,and C++ language for programming,performances on various multi-core processor computers are compared among the three implementations together with the original sequential forms.We prove that with the increment of processor's cores and the number of threads accordingly,the parallel algorithms will efficiently reduce the number of vertex of a polyline and generate multi-resolution polyline data,which dramatically speed up the process of map generalization and thus real-time display effects are achieved.
- cartographic generalization /
- Douglas-Peucker algorithm /
- parallel algorithm /
- multi-core processor /
- sequential algorithm

[1]	杜佳威, 武芳, 行瑞星, 李彩霞, 李靖涵. 几种具有编解码结构的深度学习模型在建筑物综合中的应用与比较 . 武汉大学学报 ● 信息科学版, 2022, 47(7): 1052-1062. doi: 10.13203/j.whugis20200143
[2]	武芳, 杜佳威, 钱海忠, 翟仁健. 地图综合智能化研究的发展与思考 . 武汉大学学报 ● 信息科学版, 2022, 47(10): 1675-1687. doi: 10.13203/j.whugis20210687
[3]	崔家武, 周波阳, 罗志才, 张兴福. 利用MPI并行算法实现球谐综合的效率分析 . 武汉大学学报 ● 信息科学版, 2019, 44(12): 1802-1807. doi: 10.13203/j.whugis20180165
[4]	黄伟明, 杨建宇, 陈彦清, 张毅, 张睿. 基于扇形筛选法的矢量数据压缩方法 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 487-491. doi: 10.13203/j.whugis20140225
[5]	刘远刚, 郭庆胜, 孙雅庚, 杨乃, 郑春燕. 地图自动综合中Beams移位算法的实现与改进 . 武汉大学学报 ● 信息科学版, 2016, 41(4): 450-454,540. doi: 10.13203/j.whugis20140343
[6]	刘远刚, 郭庆胜, 孙雅庚, 林青, 郑春燕. 地图目标群间骨架线提取的算法研究 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 264-268.
[7]	成晓强, 艾廷华, 杨敏. 一种决策驱动的地图综合服务语义增强方法 . 武汉大学学报 ● 信息科学版, 2014, 39(5): 561-565. doi: 10.13203/j.whugis20120208
[8]	翁杰, 郭庆胜, 王晓妍, 刘鹏. 一种改进的图斑合并算法 . 武汉大学学报 ● 信息科学版, 2012, 37(9): 1116-1119.
[9]	翟晓芳, 龚健雅, 肖志峰, 张丙龙. 利用流水线技术的遥感影像并行处理 . 武汉大学学报 ● 信息科学版, 2011, 36(12): 1430-1433.
[10]	艾廷华, 杨帆, 李精忠. 第二次土地资源调查数据建库中的土地利用图综合缩编 . 武汉大学学报 ● 信息科学版, 2010, 35(8): 887-891.
[11]	何津, 费立凡. 再论三维Douglas-Peucker算法及其在DEM综合中的应用 . 武汉大学学报 ● 信息科学版, 2008, 33(2): 160-163.
[12]	艾廷华, 梁蕊. 导航电子地图的变比例尺可视化 . 武汉大学学报 ● 信息科学版, 2007, 32(2): 127-130.
[13]	陈军, 胡云岗, 赵仁亮, 李志林. 道路数据缩编更新的自动综合方法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(11): 1022-1027.
[14]	蔡永香, 郭庆胜. 基于Kohonen网络的点群综合研究 . 武汉大学学报 ● 信息科学版, 2007, 32(7): 626-629.
[15]	艾廷华, 郭宝辰, 黄亚峰. 1∶5万地图数据库的计算机综合缩编 . 武汉大学学报 ● 信息科学版, 2005, 30(4): 297-300.
[16]	艾廷华, 刘耀林. 土地利用数据综合中的聚合与融合 . 武汉大学学报 ● 信息科学版, 2002, 27(5): 486-492.
[17]	艾廷华, 郭仁忠. 支持地图综合的面状目标约束Delaunay三角网剖分 . 武汉大学学报 ● 信息科学版, 2000, 25(1): 35-41.
[18]	粟松廷. 单级比例尺电子地图数据库多级表现系统的设计 . 武汉大学学报 ● 信息科学版, 1999, 24(2): 158-161.
[19]	郭庆胜. 线状要素图形综合的渐进方法研究 . 武汉大学学报 ● 信息科学版, 1998, 23(1): 52-56.
[20]	闫浩文, 张鑫港, 禄小敏, 李蓬勃. DP算法自动实现方法—以河流化简为例 . 武汉大学学报 ● 信息科学版, 0, 0(0): 0-0. doi: 10.13203/j.whugis20210412

点击查看大图

计量

文章访问数: 1072
HTML全文浏览量: 42
PDF下载量: 403
被引次数: 0

利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素

¹南京大学地理信息科学系,南京市汉口路22号210093;²南京师范大学地理科学学院,南京市文苑路1号210046;³南京师范大学虚拟地理环境教育部重点实验室,南京市文苑路1号210046

基金项目: 国家自然科学基金资助项目(41071288)

作者简介:
马劲松，副教授，博士，主要从事地图学和３ＤＧＩＳ的教学与研究。目前已经发表学术论文６０多篇。

收稿日期: 2011-10-21
刊出日期: 2011-12-05

中图分类号: P283.1;P208

关键词:

摘要: Douglas-Peucker算法是线要素简化的经典算法,针对其存在大量计算、难以做到实时的缺点,运用并行技术实现Douglas-Peucker算法,并在多核处理器的计算机上进行实验,验证了并行算法的效率与实时性。

English Abstract

A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers

¹ Department of Geographic Information Science,Nanjing University,22 Hankou Road,Nanjing 210093,China;² Institute of Geographic Science,Nanjing Normal University,1 Wenyuan Road,Nanjing 210046,China;³Key Laboratory of Virtual Geographic Environment of Ministry of Education,Nanjing Normal University, 1 Wenyuan Road,Nanjing 210046,China

Funds: 国家自然科学基金资助项目(41071288)

Received Date: 2011-10-21
Publish Date: 2011-12-05

Keywords:

Abstract: The Douglas-Peucker polyline simplification algorithm has been widely adopted in map generalization for decades,though it is often criticized for its low performance.As multi-core processor computers become widely available,it might be a good opportunity to improve the performance by converting its sequential implementation to parallel form.We present three different parallel implementations of the Douglas-Peucker algorithm.The first is in either recursive or non-recursive manner using OpenMP.The second is done by splitting a polyline feature into irrelevant segments and distributing segments to parallel threads.The third method is to dispatch each polyline feature to an idle parallel thread in which the conventional sequential method is applied.By utilizing the official China's provincial boundary geospatial data set,and C++ language for programming,performances on various multi-core processor computers are compared among the three implementations together with the original sequential forms.We prove that with the increment of processor's cores and the number of threads accordingly,the parallel algorithms will efficiently reduce the number of vertex of a polyline and generate multi-resolution polyline data,which dramatically speed up the process of map generalization and thus real-time display effects are achieved.

马劲松, 沈婕, 徐寿成. 利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J]. 武汉大学学报 ● 信息科学版, 2011, 36(12): 1423-1426.

引用本文:

马劲松, 沈婕, 徐寿成. 利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素[J]. 武汉大学学报 ● 信息科学版, 2011, 36(12): 1423-1426.

Citation:

MA Jinsong, SHEN Jie, XU Shoucheng. A Parallel Implementation of Douglas-Peucker Algorithm for Real-Time Map Generalization of Polyline Features on Multi-core Processor Computers[J]. Geomatics and Information Science of Wuhan University, 2011, 36(12): 1423-1426.