基于偏移四叉树投票的“大尺寸”点状符号多尺度无压盖可视化

doi:10.11947/j.AGCS.2016.20150446

测绘学报 ›› 2016, Vol. 45 ›› Issue (8): 983-991.doi: 10.11947/j.AGCS.2016.20150446

基于偏移四叉树投票的“大尺寸”点状符号多尺度无压盖可视化

张翔¹, 王少东², 王玉霞³

1. 武汉大学资源与环境科学学院, 湖北武汉 430079;
2. 中国科学院软件研究所计算机科学国家重点实验室, 北京 100190;
3. 北京大学遥感与地理信息系统研究所, 北京100871

收稿日期:2015-08-30 修回日期:2016-06-23 出版日期:2016-08-20 发布日期:2016-08-31
作者简介:张翔(1982-),男,博士,副教授,研究方向为志愿者地理信息处理与可视化。E-mail:xiang.zhang@whu.edu.cn
基金资助:
国家自然科学基金（41301410）；国家863计划（2015AA123901）；国家基础科学人才培养基金（J1103409）

Clutter-free Visualization of Large Point Symbols at Multiple Scales by Offset Quadtrees

ZHANG Xiang¹, WANG Shaodong², WANG Yuxia³

1. School of Resources and Environmental Sciences, Wuhan University, Wuhan 430079, China;
2. Institute of Software Chinese Academy of Sciences, Beijing 100190, China;
3. Institute of Remote Sensing and Geographical Information Systems, Peking University, Beijing 100871, China

Received:2015-08-30 Revised:2016-06-23 Online:2016-08-20 Published:2016-08-31
Supported by:
The National Natural Science Foundation of China (No. 41301410);The National High-tech Research and Development Program of China (863 Program) (No. 2015AA123901);The Project for National Basic Science Personnel Training Fund(No. J1103409)

摘要/Abstract

摘要： 为解决Web 2.0环境下点状符号地图混搭中的制图问题，本文研究并实现了一种可100%避免压盖的“大尺寸”点符号高效可视化方法。该方法的核心思想是四叉树网格单选，采用网格平移对多次单选结果投票来计算符号在各缩放级别的显著性等级，可解决符号在相邻网格的空间冲突。该过程不需要显式探测冲突，因而处理效率极高。随着地图放大，重要性较低的符号也逐级显现，实现了语义层次的多尺度表达。针对符号和网格大小比率关系、有效网格平移方案及图面利用率不足问题提出两种扩展：格网增选和多级符号叠加。对方法的可行性进行了试验验证，并分析了该方法在用户查询条件改变下的稳定性和不同数据量下的伸缩性（非优化实现可达到10⁵量级数据的亚秒级处理）。

关键词: 空间冲突消解, 多尺度可视化, 大尺寸符号, 四叉树, 实时Web制图

Abstract: To address the cartographic problems in map mash-up applications in the Web 2.0 context, this paper studies a clutter-free technique for visualizing large symbols on Web maps. Basically, a quadtree is used to select one symbol in each grid cell at each zoom level. To resolve the symbol overlaps between neighboring quad-grids, multiple offsets are applied to the quadtree and a voting strategy is used to compute the significant level of symbols for their selection at multiple scales. The method is able to resolve spatial conflicts without explicit conflict detection, thus enabling a highly efficient processing. Also the resulting map forms a visual hierarchy of semantic importance. We discuss issues such as the relative importance, symbol-to-grid size ratio, and effective offset schemes, and propose two extensions to make better use of the free space available on the map. Experiments were carried out to validate the technique,which demonstrates its robustness and efficiency (a non-optimal implementation leads to a sub-second processing for datasets of a 10⁵ magnitude).

Key words: clutter reduction, multi-scale visualization, large symbols, quadtree, real-time Web mapping

中图分类号:

P208

张翔, 王少东, 王玉霞. 基于偏移四叉树投票的“大尺寸”点状符号多尺度无压盖可视化[J]. 测绘学报, 2016, 45(8): 983-991.

ZHANG Xiang, WANG Shaodong, WANG Yuxia. Clutter-free Visualization of Large Point Symbols at Multiple Scales by Offset Quadtrees[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(8): 983-991.

参考文献

[1] ROICK O,HEUSER S.Location Based Social Networks:Definition,Current State of the Art and Research Agenda[J].Transactions in GIS,2013,17(5):763-784.
[2] FIELD K,O'BRIEN J.Cartobiography:Experiments in Using and Organising the Spatial Context of Micro-blogging[J].Transactions in GIS,2010,14(S1):5-23.
[3] KORPI J,AHONEN-RAINIO P.Clutter Reduction Methods for Point Symbols in Map Mashups[J].The Cartographic Journal,2013,50(3):257-265.
[4] ELLIS G,DIX A.A Taxonomy of Clutter Reduction for Information Visualisation[J].IEEE Transactions on Visualization and Computer Graphics,2007,13(6):1216-1223.
[5] 艾廷华,刘耀林.保持空间分布特征的群点化简方法[J].测绘学报,2002,31(2):175-181.AI Tinghua,LIU Yaolin.A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J].Acta Geodaetica et Cartographica Sinica,2002,31(2):175-181.
[6] 蔡永香,郭庆胜.基于Kohonen网络的点群综合研究[J].武汉大学学报(信息科学版),2007,32(7):626-629.CAI Yongxiang,GUO Qingsheng.Points Group Generalization Based on Konhonen Net[J].Geomatics and Information Science of Wuhan University,2007,32(7):626-629.
[7] DE BERG M,BOSE P,CHEONG O,et al.On Simplifying Dot Maps[J].Computational Geometry,2004,27(1):43-62.
[8] 邓红艳,武芳,钱海忠,等.基于遗传算法的点群目标选取模型[J].中国图象图形学报,2003,8(8):970-976.DENG Hongyan,WU Fang,QIAN Haizhong,et al.A Model of Point Cluster Selection Based on Genetic Algorithms[J].Journal of Image and Graphics,2003,8(8):970-976.
[9] TÖPFER F,PILLEWIZER W.The Principles of Selection[J].The Cartographic Journal,1966,3(1):10-16.
[10] BEEN K,NÖLLENBURG M,POON S H,et al.Optimizing Active Ranges for Consistent Dynamic Map Labeling[J].Computational Geometry,2010,43(3):312-328.
[11] SCHWARTGES N,ALLERKAMP D,HAUNERT J,et al.Optimizing Active Ranges for Point Selection in Dynamic Maps[C]//Proceedings of the 16th ICA Generalisation Workshop (ICAGW'13).Dresden:Bib Sonomy,2013.
[12] 艾廷华,成建国.对空间数据多尺度表达有关问题的思考[J].武汉大学学报(信息科学版),2005,30(5):377-382.AI Tinghua,CHENG Jianguo.Key Issues of Multi-scale Representation of Spatial Data[J].Geomatics and Information Science of Wuhan University,2005,30(5):377-382.
[13] VAN OOSTEROM,P.Variable-scale Topological Data Structures Suitable for Progressive Data Transfer:The Gap-face Tree and Gap-edge Forest[J].Cartography and Geographic Information Science,2005,32(4):331-346.
[14] NUTANONG S,ADELFIO M D,SAMET H.Multiresolution Select-distinct Queries on Large Geographic Point Sets[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems.New York,NY:ACM,2012:159-168.
[15] SARMA A D,LEE H,GONZALEZ H,et al.Efficient Spatial Sampling of Large Geographical Tables[C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.New York,NY:ACM,2012:193-204.
[16] BEREUTER P,WEIBEL R.Real-time Generalization of Point Data in Mobile and Web Mapping Using Quadtrees[J].Cartography and Geographic Information Science,2013,40(4):271-281.
[17] KOVANEN J,SARJAKOSKI L T.Sequential Displacement and Grouping of Point Symbols in a Mobile Context[J].Journal of Location Based Services,2013,7(2):79-97.
[18] 杨敏,艾廷华,卢威,等.自发地理信息兴趣点数据在线综合与多尺度可视化方法[J].测绘学报,2015,44(2):228-234.DOI:10.11947/j.AGCS.2015.20130564.YANG Min,AI Tinghua,LU Wei,et al.A Real-time Generalization and Multi-scale Visualization Method for POI Data in Volunteered Geographic Information[J].Acta Geodaetica et Cartographica Sinica,2015,44(2):228-234.DOI:10.11947/j.AGCS.2015.20130564.
[19] HARRIE L,SARJAKOSKI T,LEHTO L.A Mapping Function for Variable-scale Maps in Small-display Cartography[J].Journal of Geospatial Engineering,2002,4(2):111-123.
[20] HAUNERT J H,SERING L.Drawing Road Networks with Focus Regions[J].IEEE Transactions on Visualization and Computer Graphics,2011,17(12):2555-2562.
[21] SHNEIDERMAN B.The Eyes Have It:A Task by Data Type Taxonomy for Information Visualizations[C]//Proceedings of the IEEE Symposium on Visual Languages.Boulder,CO:IEEE,1996:336-343.

基于偏移四叉树投票的“大尺寸”点状符号多尺度无压盖可视化

Clutter-free Visualization of Large Point Symbols at Multiple Scales by Offset Quadtrees

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	胡佰林, 王春波, 赵学胜, 崔马军. 基于WGS-84椭球面的退化四叉树经纬线格网剖分[J]. 测绘学报, 2016, 45(S1): 32-39.
[2]	喻金桃, 郭海涛, 李传广, 卢俊, 姜春雪. 四叉树与多种活动轮廓模型相结合的遥感影像水边线提取方法[J]. 测绘学报, 2016, 45(9): 1104-1114.
[3]	郭海涛, 孙磊, 申家双, 陈小卫, 张宏伟. 一种四叉树和测地线活动轮廓模型相结合的海陆影像分割方法[J]. 测绘学报, 2016, 45(1): 65-72.
[4]	杨敏, 艾廷华, 卢威, 成晓强, 周启. 自发地理信息兴趣点数据在线综合与多尺度可视化方法[J]. 测绘学报, 2015, 44(2): 228-234.
[5]	张静张勤赵超英张菊清. 顾及协方差函数的自适应四叉树InSAR数据压缩算法[J]. 测绘学报, 2014, 43(5): 486-492.
[6]	赵学胜,范德芹,王娇娇,王磊. 退化四叉树格网的全球多分辨率DEM无缝表达[J]. 测绘学报, 2012, 41(6): 918-925.
[7]	刘扬,宫阿都,李京. 基于数据分层分块的海量三维地形四叉树简化模型[J]. 测绘学报, 2010, 39(4): 0-440.