小规模地理场景中点要素三维注记优化配置算法

doi:10.11947/j.AGCS.2016.20160210

测绘学报 ›› 2016, Vol. 45 ›› Issue (12): 1476-1484.doi: 10.11947/j.AGCS.2016.20160210

小规模地理场景中点要素三维注记优化配置算法

周鑫鑫, 吴长彬, 孙在宏, 丁远, 贺涛

南京师范大学虚拟地理环境教育部重点实验室, 江苏南京 210046

收稿日期:2016-05-03 修回日期:2016-10-11 出版日期:2016-12-20 发布日期:2017-01-02
通讯作者: 吴长彬 E-mail:wuchangbin@njnu.edu.cn
作者简介:周鑫鑫(1991-),男,硕士,研究方向为三维地籍及地图制图。E-mail:windofmay@foxmail.com
基金资助:
国家自然科学基金（41471318）

A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene

ZHOU Xinxin, WU Changbin, SUN Zaihong, DING Yuan, HE Tao

Key Laboratory of Virtual Geographic Environment, Ministry of Education, Nanjing Normal University, Nanjing 210046, China

Received:2016-05-03 Revised:2016-10-11 Online:2016-12-20 Published:2017-01-02
Supported by:
The National Natural Science Foundation of China (No.41471318)

摘要/Abstract

摘要： 地理场景中点要素三维注记配置规则多为“遮挡则不显示”和“遮挡直接显示”，该类规则的缺陷是注记信息丢失或存在大量遮挡，普适性不强，尤其不适用于小规模地理场景点要素三维注记配置。本文首先归纳了三维注记绘制的内容、位置及方法，并针对小规模地理场景点要素三维注记配置问题，以“信息不丢失、注记尽可能少的遮挡”为配置目标，配置规则为“遮挡后优化并显示”。算法以透视变换矩阵、逆透视变换矩阵及GRID算法为基础，以遗传算法为核心，以三维注记质量评价函数为遗传算法适应度评价函数，实现点要素三维注记的可行最优解求解。经多视角、多平台对照试验可知，本算法适用于多视角三维注记优化配置，具备普适性；与主流GIS平台（SuperMap Desktop、ArcScene）的三维注记配置效果作对比，本算法三维注记质量值分别相对提升144%、232%，符合配置目标。

关键词: 地理场景, 三维注记, 三维注记配置, 遗传算法, 注记质量评价函数, GRID算法

Abstract: The 3D annotations placement rules of point features in geographic scene are "obscured then not showing" and "obscured then directly showing" normally. The defects of those rules are annotation information lost or large numbers of occlusion, so their universalities are not strong and they are not suitable for the annotation placement of small-scaled geographic scene. This paper summarizes the contents, position and placement methods of 3D annotation and takes the aim at "not loss of annotation information and less annotation obscured as far as possible" of the research problem of the annotation placement of small-scaled geographic scene. The configuration rule of 3D annotation Identifies as "obscured then optimized to display". The designed algorithm based on the perspective transformation matrix, the inverse perspective transformation matrix and the grid algorithm takes the genetic algorithm (GA) whose fitness evaluation function uses the 3D Annotation quality evaluation function as the core to realize the feasible optimal solution of 3D annotations of point features in geographic scene. By the multi-views, multi-platforms contrast experiment, this algorithm is applicable for multi-views 3D annotation placement widely. The 3D annotation effect is better than mainstream GIS platforms (such as SuperMap desktop, ArcScene), which assumes that the algorithm's 3D annotation quality value is relatively increased 144%, 232%. The algorithm fits in with the target configuration.

Key words: geographic scene, 3D annotation, 3D annotation placement, genetic algorithm, 3D annotation quality evaluation function, GRID algorithm

中图分类号:

P208

周鑫鑫, 吴长彬, 孙在宏, 丁远, 贺涛. 小规模地理场景中点要素三维注记优化配置算法[J]. 测绘学报, 2016, 45(12): 1476-1484.

ZHOU Xinxin, WU Changbin, SUN Zaihong, DING Yuan, HE Tao. A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(12): 1476-1484.

参考文献

[1] CHEN Chen, ZHANG Liqiang, MA Jingtao, et al. Adaptive Multi-resolution Labeling in Virtual Landscapes[J]. International Journal of Geographical Information Science, 2010, 24(6):949-964.
[2] 乔占明, 闫浩文.地图标注和地图注记的探讨[J]. 测绘与空间地理信息, 2011, 34(1):205-207. QIAO Zhanming, YAN Haowen. Discussion on Map Labeling and Map Annotation[J]. Geomatics and Spatial Information Technology, 2011, 34(1):205-207.
[3] RIBEIRO G M, LORENA L A N. Lagrangean Relaxation with Clusters for Point-feature Cartographic Label Placement Problems[J]. Computers & Operations Research, 2008, 35(7):2129-2140.
[4] PEREIRA G S, NOGUEIRA LORENA L A, MATTOS RIBEIRO G. A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems[J]. Geographical Analysis, 2016, 48(1):43-58.
[5] RABELLO R L, MAURI G R, RIBEIRO G M, et al. A Clustering Search Metaheuristic for the Point-Feature Cartographic Label Placement Problem[J]. European Journal of Operational Research, 2014, 234(3):802-808.
[6] 王昭, 吴中恒, 费立凡, 等. 基于几何信息熵的面状要素注记配置[J]. 测绘学报, 2009, 38(2):183-188. DOI:10.3321/j.issn:1001-1595.2009.02.015. WANG Zhao, WU Zhongheng, FEI Lifan, et al. Automatic Name Placement of Area Feature:A Metric Information Approach[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2):183-188. DOI:10.3321/j.issn:1001-1595.2009.02.015.
[7] 张志军, 李霖, 于忠海, 等. 散列式面状注记自动配置技术研究[J]. 武汉大学学报(信息科学版), 2011, 36(6):739-742. ZHANG Zhijun, LI Lin, YU Zhonghai, et al. Auto-Labeling of Hash Anea Features[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6):739-742.
[8] 张志军. 基于规则引擎的地图注记自动配置方法研究[D]. 武汉:武汉大学, 2011. ZHANG Zhijun. Research on Automatic Label Placement Based on Rules-Engine[D]. Wuhan:Wuhan University, 2011.
[9] 吴长彬, 闾国年, 刘昱君. 基于规则库和网格算法的土地利用现状图自动数字注记[J]. 测绘学报, 2008, 37(2):250-255. DOI:10.3321/j.issn:1001-1595.2008.02.021. WU Changbin, LU Guonian, LIU Yujun. Automated Numeric Placement for Land Utilization Map Based on Rule Database and Grid Algorithm[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2):250-255. DOI:10.3321/j.issn:1001-1595.2008.02.021.
[10] RYLOV M A,REIMER A W. Improving Label Placement Quality by Considering Basemap Detail with a Raster-based Approach[J]. Geoinformatica, 2015, 19(3):463-486.
[11] MAASS S, DÖLLNER J. Dynamic Annotation of Interactive Environments Using Object-integrated Billboards[C]//Proceedings of the 14th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision. Plzen, Czech Republic:WSCG, 2006:327-334.
[12] MAASS S, DVLLNER J. Embedded Labels for Line Features in Interactive 3D Virtual Environments[C]//Proceedings of the 5th International Conference on Computer Graphics, Virtual Reality, Visualisation and Interaction in Africa. New York, NY, USA:ACM, 2007:53-59.
[13] VAARANIEMI M, FREIDANK M, WESTERMANN R. Enhancing the Visibility of Labels in 3D Navigation Maps[M]//POULIOT J, DANIEL S, HUBERT F, et al. Progress and New Trends in 3D Geoinformation Sciences. Berlin Heidelberg:Springer, 2013:23-40.
[14] VAARANIEMI M,TREIB M, WESTERMANN R. Temporally Coherent Real-time Labeling of Dynamic Scenes[C]//Proceedings of the 3rd International Conference on Computing for Geospatial Research and Applications. New York, NY, USA:ACM, 2012:17.
[15] PRADO R D, RAPOSO A B. Real-time Label Visualization in Massive CAD Models[C]//Proceedings of 2013 International Conference on Computer-aided Design and Computer Graphics. Guangzhou, China:IEEE, 2013:337-344.
[16] 杨乃. 基于空间认知的三维地图设计若干问题的研究[D]. 武汉:武汉大学, 2010. YANG Nai. Study on Several Issues of 3D Map Design Based on Spatial Cognition[D]. Wuhan:Wuhan University, 2010.
[17] 胡斌, 江南, 邹志强, 等. 大规模室外动态场景调度机制研究[J]. 地球信息科学, 2007, 9(5):8-13. HU Bin, JIANG Nan, ZOU Zhiqiang, et al. Research on Dispatch of Dynamic Scene in Large Scope Outdoor Environment[J]. Geo-information Science, 2007, 9(5):8-13.
[18] RIBEIRO G M, LORENA L A N. Heuristics for Cartographic Label Placement Problems[J]. Computers & Geosciences, 2006, 32(6):739-748.
[19] STRIJK T, VERWEIJ B, AARDAL K. Algorithms for Maximum Independent Set Applied to Map Labelling[J]. Utrecht:Department of Computer Science, Utrecht University, 2000.
[20] 樊红, 张祖勋, 杜道生. 地图注记质量评价模型的研究[J]. 测绘学报, 2004, 33(4):362-366. DOI:10.3321/j.issn:1001-1595.2004.04.016. FAN Hong, ZHANG Zuxun, DU Daosheng. The Study of the Evaluation Model for Map Labeling[J]. Acta Geodaetica et Cartographica Sinica, 2004, 33(4):362-366. DOI:10.3321/j.issn:1001-1595.2004.04.016.
[21] PITTEWAY M L V, WATKINSON D J. Bresenham's Algorithm with Grey Scale[J]. Communications of the ACM, 1980, 23(11):625-626.
[22] ŽALIK B, KOLINGEROVA I. A Cell-based Point-in-polygon Algorithm Suitable for Large Sets of Points[J]. Computers & Geosciences, 2001, 27(10):1135-1145.
[23] CHRISTENSEN J,MARKS J, SHIEBER S. An Empirical Study of Algorithms for Point-feature Label Placement[J]. ACM Transactions on Graphics, 1995, 14(3):203-232.
[24] 史云飞, 郭仁忠, 李霖, 等. 四维地籍的建立与分析[J]. 武汉大学学报(信息科学版), 2014, 39(3):322-326. SHI Yunfei,GUO Renzhong, LI Lin, et al. Establishment and Analysis of 4D Cadastre[J]. Geomatics and Information Science of Wuhan University, 2014, 39(3):322-326.

小规模地理场景中点要素三维注记优化配置算法

A 3D Annotation Optimal Placement Algorithm for the Point Features in the Small Scale Geographic Scene

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	纪雪, 唐秋华, 陈义兰, 李杰, 丁德秋. 联合支持向量机和增强学习算法的多波束声学底质分类[J]. 测绘学报, 2021, 50(7): 972-981.
[2]	刘远刚, 李少华, 蔡永香, 何贞铭, 马潇雅, 李鹏程, 郭庆胜, 何宗宜. 移位安全区约束下的建筑物群移位免疫遗传算法[J]. 测绘学报, 2021, 50(6): 812-822.
[3]	王华斌, 韩旻, 王光辉, 李玉. 遥感影像要素提取的可变结构卷积神经网络方法[J]. 测绘学报, 2019, 48(5): 583-596.
[4]	闫利, 谭骏祥, 刘华, 陈长军. 融合遗传算法和ICP的地面与车载激光点云配准[J]. 测绘学报, 2018, 47(4): 528-536.
[5]	张海波, 汪长城, 朱建军, 付海强. 利用ESAR极化数据的复杂地形区森林地上生物量估算[J]. 测绘学报, 2018, 47(10): 1353-1362.
[6]	刘丽峰, 杨飞, 张树清, 孔维华, 王殷行. 应用人工免疫算法快速规划3D TF/TA²航线[J]. 测绘学报, 2015, 44(4): 462-470.
[7]	余丽陆锋. 交通网络旅行商路径优化的遗传禁忌搜索算法[J]. 测绘学报, 2014, 43(11): 1197-1203.
[8]	于海璁陆锋. 一种基于遗传算法的多模式多标准路径规划方法[J]. 测绘学报, 2014, 43(1): 89-96.
[9]	童晓冲贲进汪滢. 利用数值投影变换构建全球六边形离散格网[J]. , 2013, 42(2): 268-276.
[10]	王家耀，谢明霞，郭建忠，陈科. 基于相似性保持和特征变换的高维数据聚类改进算法[J]. 测绘学报, 2011, 40(3): 269-275.
[11]	刘洋,兰泽英,刘耀林. 基于多目标遗传优化的等值区域图分级算法研究[J]. 测绘学报, 2010, 39(2): 0-145.
[12]	刘汉丽周成虎朱阿兴李霖. 多子群遗传神经网络模型用于路口短时交通流量预测 [J]. 测绘学报, 2009, 38(4): 0-310.