地图点要素注记自动配置中聚类分组的蚁群算法应用  

Automatic Label Placement of Point Feature:Using Ant Colony Algorithm Based on Group Clustering

作　　者：周鑫鑫[1] 孙在宏[1] 吴长彬[1] 丁远[1] 

机构地区：[1]南京师范大学虚拟地理环境教育部重点实验室,南京210046

出　　处：《地球信息科学学报》2015年第8期902-908,共7页Journal of Geo-information Science

基　　金：国家自然科学基金项目"不动产统一登记驱动下的地籍混合维度空间数据表达模型研究"(41471318)

摘　　要：大规模点要素注记自动配置问题是地图注记的难点之一,主要受限于时间效率和注记配置质量。针对该问题,本文首先提出一种椭圆形多方位多级注记待选方位配置方案,使其参数化、多元化。其次,结合点要素空间分布特征,提出一种以聚类分组的蚁群算法,并讨论和优化核心参数,实现大规模点要素的注记快速配置。实验表明,该算法计算效率明显提升,算法性能稳定。针对注记密度在5%~30%随机分布点要素的地图,其相比传统蚁群算法算法效率提高73.2%;同时,该算法的注记结果质量比传统蚁群算法注记结果质量好,注记适应度提升8.0%。实验采用抚顺县集体土地所有权界址点数据进行验证,结果表明效率提升86.7%,且注记适应度提升14.6%。本算法适用于点要素规模大、点簇疏密变化差异大的点要素注记自动配置问题的快速求解。The problem of Large-scaled Point Feature Cartographic Label Placement（LS-PFCLP） is one of map labeling difficulties, which is mainly limited by time efficiency and labels＇ quality. Changing this plight will accelerate the application development of Intelligent Cartography. The article firstly contraposes the form simplification of traditional potential label position scheme and puts forward an oval multi-orientations and multi-levels cartographic potential label position scheme to make a better conformation of the potential label position scheme to the actual demand, and make it parameterized and multiplex. Secondly, the article combines the space distribution features of point features to adopt an Ant Colony Algorithm based on cluster grouping（C-ACA）, whose core framework is decreasing the large scale of points to plural mini-scaled point collections through DBSCAN clustering, then integrating Ant Colony Algorithm to C-ACA. In the process of C-ACA＇s implementation, we discuss and optimize the core parameters, such as Eps and Min Pts of DBSCAN, ant colony size parameters（ Pa、ηcj、τcj、Pbcj）, and evaluation function of E（bc）, to achieve Large-scaled Point Feature Cartographic Label Placement. Experiments show that C- ACA has a great contribution to the efficiency improvement of LS- PFCLP.When compared, with two cases of random points tests and one realistic boundary points case, with techniques such as Ant Colony Algorithm（ACA）, the C-ACA has been proven to be an efficient choice, with better performance in both efficiency and quality. In case 1, The C-ACA improves the efficiency by 73.2 percent than normalACA, when the label density falls in between 5% and 30%. Moreover, the altered resultant label＇quality is 8.0percent better than before. In case 2, the result of C- ACA has justified the stability presentation. In case 3, we have used this algorithm to process the boundary points of the collective land ownership data of Fushun county in China, which has improved the efficiency by

关 键 词：点要素注记 聚类分组 蚁群算法 注记配置方案 注记适应度评价函数 

分 类 号：P282[天文地球—地图制图学与地理信息工程]