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

doi:10.11947/j.AGCS.2016.20160210

Abstract

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

CLC Number:

P208

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.

References

[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.