基于Voronoi图的点群移位算法效率优化研究-工程技术版.PDF

第 １６卷第４期 南京师范大学学报(工程技术版) Ｖｏｌ１６ Ｎｏ４ ２０１６年１２月 ＪＯＵＲＮＡＬ ＯＦ ＮＡＮＪＩＮＧ ＮＯＲＭＡＬ ＵＮＩＶＥＲＳＩＴＹ(ＥＮＧＩＮＥＥＲＩＮＧ ＡＮＤＴＥＣＨＮＯＬＯＧＹ ＥＤＩＴＩＯＮ) Ｄｅｃꎬ２０１６ － ｄｏｉ:１０.３９６９/ ｊ.ｉｓｓｎ.１６７２ １２９２.２０１６.０４.００９ 基于 Ｖｏｒｏｎｏｉ 图的点群移位算法效率优化研究 １ ２ꎬ３ ２ꎬ３ ２ꎬ３ 王孟和 ꎬ杨　 帅 ꎬ张彭涛 ꎬ沈　 婕 (１.南京市测绘勘察研究院有限公司ꎬ江苏 南京 ２１００１９) (２.南京师范大学地理科学学院ꎬ江苏 南京 ２１００２３) (３.南京师范大学虚拟地理环境教育部重点实验室ꎬ江苏 南京 ２１００２３) [摘要]　 点群移位算法是点综合算法中一个重要的方法ꎬ可以解决因比例尺缩放和符号化后引起的要素空间 冲突ꎬ但由于目前点群移位算法效率较低ꎬ难以满足快速地图成图的要求. 本文在分析已有点群移位算法效率的 基础上ꎬ选择了基于Ｖｏｒｏｎｏｉ 图的点群移位算法ꎬ并从算法级和代码级两方面对其进行了效率优化. 实验表明ꎬ本 文提出的优化方法ꎬ在保持点群移位结果可用性的前提下ꎬ可以提高点群移位算法的效率. [关键词]　 移位算法ꎬ算法优化ꎬ点群ꎬＶｏｒｏｎｏｉ － － － [中图分类号]Ｐ２０８　 [文献标志码]Ａ　 [文章编号]１６７２ １２９２(２０１６)０４ ００５２ ０５ Ｓｔｕｄｙ ｏｎ Ｅｆｆｉｃｉｅｎｃｙ Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｐｏｉｎｔ￣Ｃｌｕｓｔｅｒ Ｄｉｓｐｌａｃｅｍｅｎｔ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｖｏｒｏｎｏｉ Ｄｉａｇｒａｍ １ ２ꎬ３ ２ꎬ３ ２ꎬ３ Ｗａｎｇ Ｍｅｎｇｈｅ ꎬＹａｎｇ Ｓｈｕａｉ ꎬＺｈａｎｇ Ｐｅｎｇｔａｏ ꎬＳｈｅｎＪｉｅ (１.Ｎａｎｊｉｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ ＳｕｒｖｅｙｉｎｇꎬＭａｐｐｉｎｇ ＆ Ｇｅｏｔｅｃｈｎｉｃａｌ ＩｎｖｅｓｔｉｇａｔｉｏｎꎬＣｏ.ꎬＬｔｄ.ꎬＮａｎｊｉｎｇ２１００１９ꎬＣｈｉｎａ) (２.Ｓｃｈｏｏｌ ｏｆ Ｇｅｏｇｒａｐｈｙ ＳｃｉｅｎｃｅꎬＮａｎｊｉｎｇ Ｎｏｒｍａｌ ＵｎｉｖｅｒｓｉｔｙꎬＮａｎｊｉｎｇ２１００２３ꎬＣｈｉｎａ) (３.Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｖｉｒｔｕａｌ Ｇｅｏｇｒａｐｈｉｃ ＥｎｖｉｒｏｎｍｅｎｔꎬＭｉｎｉｓｔｒｙ ｏｆ ＥｄｕｃａｔｉｏｎꎬＮａｎｊｉｎｇ Ｎｏｒｍａｌ ＵｎｉｖｅｒｓｉｔｙꎬＮａｎｊｉｎｇ２１００２３ꎬＣｈｉｎａ) Ａｂｓｔｒａｃｔ:Ｐｏｉｎｔ￣ｃｌｕｓｔｅｒ ｄｉｓｐｌａｃｅｍｅｎｔ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ｓｉｇｎｉｆｉｃａｎｔ ｐａｒｔｓ ｏｆ ｍａｐ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ａｎｄｔｈｅｙ ｃａｎ ｓｏｌｖｅ ｔｈｅ ｓｐａｔｉａｌ ｃｏｎｆｌｉｃｔｓ ｃａｕｓｅｄ ｂｙ ｓｃａｌｉｎｇ ａｎｄ ｓｙｍｂｏｌｉｚａｔｉｏｎ ａｍｏｎｇ ｆｅａｔｕｒｅｓ. Ｈｏｗｅｖｅｒꎬｄｕｅ ｔｏ ｔｈｅ ｌｏｗ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ｅｘｉｓｔｉｎｇ ｐｏｉｎｔ￣ｃｌｕｓｔｅｒ ｄｉｓｐｌａｃｅｍｅｎｔ