Abstract: In traditional map visualization, point clustering is used in the display of massive map markers, but all kinds of point clustering algorithms are run-time calculations without hierarchical mechanism, and there is no filtering mechanism for map markers stack when a large number of points are scattered and displayed. In response to this problem, a solution of clustering and scattering of massive map markers is proposed based on hierarchical grid division. This method builds a K-D tree index for the center point of the hierarchical grid, and builds a quadtree index for the massive points. Through the index and storage technology, the efficient query of clustering is realized. Add grid filtering to eliminate stacking problems when massive points are scattered. The comparison is carried out on the experimental case data set, and the results show that, compared with the traditional point clustering scheme, the computing performance is significantly improved in the case of a large amount of data, and the filtering algorithm is added to the scattered display of massive markers, which effectively improves the user experience.

Key words: hierarchical grid division, map visualization, K-D tree index

摘要： 在传统的地图可视化中，面对海量地图标记物展示会采用点聚合的方式，但是各类点聚合算法都是运行时计算，没有分层机制，在海量点的散开展示时，对于地图标记物堆叠没有过滤机制。针对这一问题，提出了分层的网格划分实现海量地图标记物聚散一体化解决方案。该方法对分层网格中心点构建K-D树索引，对海量点构建四叉树索引，通过索引和存储技术，实现了聚合的高效查询。对海量点散开时增加网格过滤，消除堆叠问题。在实验案例数据集上进行对比，结果表明，与传统的点聚合方案相比，在数据量大的情况下，计算性能显著提高，对海量标记物散开展示增加过滤算法，有效提升了用户体验。

关键词: 分层网格划分, 地图可视化, K-D树索引