摘要
针对制图过程中点状要素数量巨大且分布密集的时候,传统注记配置方法无法兼顾解决注记压盖、歧义,同时减少时间耗费的问题,该文提出了一种基于图论的点状要素注记配置模型。该模型在考虑传统点状要素注记配置问题的同时,还可以附加考虑其他影响注记位置摆放的条件,并将其形式化表达为最大团问题;随后使用一种基于禁忌搜索策略的启发式算法来求解该最大团问题,从而得到注记配置问题的解;该模型有效地提高了注记配置问题的求解效率,较好地平衡了注记位置压盖和位置歧义的关系。最后,该文具体以沿道路分布的点状要素注记配置模式为例进行实验,证明了该注记自动配置模型可以有效地增强地图的可读性和美观性。
Traditional method for automated point-feature cartographic annotation could not solve the overlapping and ambiguity of annotation as well as reduce time consuming when the number of points is huge and the distribution is dense. This article proposed an automated point-feature cartographic annotation （APCA）model based on computational complexity theory and graph theory to solve the problem. In addi- tion to traditional conditions which can affect the form of APCA, this model could consider other condi- tions influencing the location and display. This paper used a planar graph to represent the relation between candidate positions and then reduced the APCA problem to the maximum clique problem （MCP）. Then the heuristic algorithm was used based on the Tabu search to solve the MCP and further to solve the point-fea- ture cartographic annotation problem. The proposed model could improve the time performance and balance the relation between overlapping and ambiguity. Finally, experiments were done on point-feature annota- tion along roads. The results showed that the proposed model could effectively enhance the readability and legibility of the map.
出处
《测绘科学》
CSCD
北大核心
2016年第4期148-153,共6页
Science of Surveying and Mapping
关键词
制图注记
最大团问题
可视化
禁忌搜索
数据密集型计算
cartographic annotation
maximum clique problem
visualization
tabu search
data-in-tensive computing
