基于模拟退火算法的地图点状要素注记配置研究
|
摘要
地图注记配置的自动化是地图制图自动化的一个重要环节,也是地图制图和GIS研究领域的热点与难点问题。地图是用小空间(地图图面)描述大空间(制图实地范围)的表达工具。这种空间的急剧缩小引起了地图要素的强烈竞争,注记既要避免相互冲突和对地理要素的相互压盖,又要达到表达清晰、美观等制图规则要求。研究表明,寻找地图的最优注记是一个NP难度问题。
本文以点状居民地要素的注记自动配置为研究对象,对此问题进行了全面系统的分析,并深入研究了地名注记问题的规则、表达模型、质量评价模型、算法及编程实现等各个方面,并基于模拟退火算法提出了一套完整的解决方案。论文的主要内容包括:
1.注记知识的系统总结
对现有的地图注记基础知识进行了系统的总结和概括,其中包括地图注记的功能、分类、要素、配置规则以及评价准则等。
2.整体最优解理论及模拟退火算法的应用
研究了注记问题的整体最优解理论,将注记问题看成是空间竞争的组合优化问题,提出了使用模拟退火算法这种全局搜索方法来求取点状要素注记配置问题的整体最优解方案。
3.注记表达模型的建立及过程实施
提出了描述点状要素自动注记配置的6元组表达模型,即:待注记要素、注记属性、注记位置、注记规则、质量评价函数以及优化算法。并将注记配置过程划分为候选位置产生、位置评价、位置选择3个关键部分分别进行实施。
4.注记质量评价模型的建立
提出了一个顾及压盖、冲突、位置优先性、要素—注记关联性4方面的地图点状要素注记质量评价模型,对应的给出了PointOver、LabelOver、PosPref、PosAsso 4个评价子函数,并联合这些子函数建立了一个质量评价总函数。
5.Voronoi图的运用
利用Voronoi图可以反映空间事物邻近性的特性,对地图平面进行Voronoi多边形剖分,并计算每个Voronoi多边形对应注记的“自由度”,以决定是否对其进行“预注记”以及如何划分“注记相关组”。
Automatic map label placement plays an important role in the automation of cartography. This problem is also active and difficult issue in cartography and GIS field. As a descriptive tool representing a large space with a small one, the map has the problem of feature space competition. On one hand, a dense map has little space for labels; on the other hand, the labels must be placed without conflicting each other or overlapping with other features. The label placement should obey to the visibility and aesthetic rules for map. Research shows that the complexity of finding the optimum label placement is a NP-hard problem.This thesis concentrates on the issue of point feature label placement (PFLP), giving a systematic and overall research on PFLP, and covering the aspects about labeling rules, labeling model, labeling algorithm, quality evaluation and experiment. Finally, a whole solution for PFLP is presented. It includes the main contents as follows:1. The Review of Map Labeling KnowledgeWe give a systematic review and summarization of the exiting labeling knowledge, which includes label function, classification, element, labeling rule and quality evaluation.2. The Global Optimization Theory and Simulated Annealing AlgorithmPFLP is regarded as a combination optimization problem for space competition.Guided by this, an optimal algorithm------Simulated Annealing Algorithm is used to findthe global optimum solution for label placement.3. The Construction of Labeling Expression Model and its OperationBy the summarization of PFLP, a six-element model is provided, which includes un-labeled feature, label property, label position, labeling rule, quality evaluation functionand labeling algorithm. And the labeling process is divided into three key parts------candidate position generation, position evaluation and position selection.4. The Research of Labeling Evaluation ModelBy analysis of the main aspects for labeling quality, an accessible labeling quality evaluation model is set up. And based on the model, the quality evaluation function is deduced.5. The Use of Voronoi DiagramWe decide whether the label should be "pre-labeled" or how to divide the labels into relative groups by the freedom of each label, which is calculated by means of Voronoi diagram.
本文以点状居民地要素的注记自动配置为研究对象,对此问题进行了全面系统的分析,并深入研究了地名注记问题的规则、表达模型、质量评价模型、算法及编程实现等各个方面,并基于模拟退火算法提出了一套完整的解决方案。论文的主要内容包括:
1.注记知识的系统总结
对现有的地图注记基础知识进行了系统的总结和概括,其中包括地图注记的功能、分类、要素、配置规则以及评价准则等。
2.整体最优解理论及模拟退火算法的应用
研究了注记问题的整体最优解理论,将注记问题看成是空间竞争的组合优化问题,提出了使用模拟退火算法这种全局搜索方法来求取点状要素注记配置问题的整体最优解方案。
3.注记表达模型的建立及过程实施
提出了描述点状要素自动注记配置的6元组表达模型,即:待注记要素、注记属性、注记位置、注记规则、质量评价函数以及优化算法。并将注记配置过程划分为候选位置产生、位置评价、位置选择3个关键部分分别进行实施。
4.注记质量评价模型的建立
提出了一个顾及压盖、冲突、位置优先性、要素—注记关联性4方面的地图点状要素注记质量评价模型,对应的给出了PointOver、LabelOver、PosPref、PosAsso 4个评价子函数,并联合这些子函数建立了一个质量评价总函数。
5.Voronoi图的运用
利用Voronoi图可以反映空间事物邻近性的特性,对地图平面进行Voronoi多边形剖分,并计算每个Voronoi多边形对应注记的“自由度”,以决定是否对其进行“预注记”以及如何划分“注记相关组”。
Automatic map label placement plays an important role in the automation of cartography. This problem is also active and difficult issue in cartography and GIS field. As a descriptive tool representing a large space with a small one, the map has the problem of feature space competition. On one hand, a dense map has little space for labels; on the other hand, the labels must be placed without conflicting each other or overlapping with other features. The label placement should obey to the visibility and aesthetic rules for map. Research shows that the complexity of finding the optimum label placement is a NP-hard problem.This thesis concentrates on the issue of point feature label placement (PFLP), giving a systematic and overall research on PFLP, and covering the aspects about labeling rules, labeling model, labeling algorithm, quality evaluation and experiment. Finally, a whole solution for PFLP is presented. It includes the main contents as follows:1. The Review of Map Labeling KnowledgeWe give a systematic review and summarization of the exiting labeling knowledge, which includes label function, classification, element, labeling rule and quality evaluation.2. The Global Optimization Theory and Simulated Annealing AlgorithmPFLP is regarded as a combination optimization problem for space competition.Guided by this, an optimal algorithm------Simulated Annealing Algorithm is used to findthe global optimum solution for label placement.3. The Construction of Labeling Expression Model and its OperationBy the summarization of PFLP, a six-element model is provided, which includes un-labeled feature, label property, label position, labeling rule, quality evaluation functionand labeling algorithm. And the labeling process is divided into three key parts------candidate position generation, position evaluation and position selection.4. The Research of Labeling Evaluation ModelBy analysis of the main aspects for labeling quality, an accessible labeling quality evaluation model is set up. And based on the model, the quality evaluation function is deduced.5. The Use of Voronoi DiagramWe decide whether the label should be "pre-labeled" or how to divide the labels into relative groups by the freedom of each label, which is calculated by means of Voronoi diagram.
引文
[1] K.A.萨里谢夫(苏),1982,地图制图学概论,测绘出版社。
[2] 张力果、赵淑梅编著,1983,地图学,高等教育出版社。
[3] 邬伦、刘瑜、张晶等,1991,地理信息系统原理、方法和应用,科学出版社。
[4] 姜美鑫、徐庆荣,1981,地形图绘制,测绘出版社。
[5] 尹贡白、王家耀、田德森、黄采芝编著,1991,地图概论,北京,测绘出版社。
[6] 王凌,2001,智能优化算法及其应用(第二章:模拟退火算法),清华大学出版社&施普林格出版社。
[7] 郭庆胜、任晓燕编制,2003,智能化地理信息处理,武汉大学出版社。
[8] 陈军,2002,Voronoi动态空间数据模型,北京,测绘出版社。
[9] 周培德,2000,计算几何——算法分析与设计,北京,清华大学出版社。
[10] 樊红,2001,地图注记自动配置的研究,博士学位论文。
[11] 罗广祥,2003,支持地图注记配置的数据模型与计算几何方法研究,博士学位论文。
[12] Alexander Wolff, Lars knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. A Simple and Efficient Algorithm for High-quality Line Labeling. GIS Research UK 7th Annual Conference: 146-150, 1999.
[13] Bernard Chazelle. Application Challenges to Computational Geometry. The Computational Geometry Impact Task Force Report, 1996.
[14] Borden D.Dent. Cartography, chapter 14. Wm.C.Brown Publishers, 1996.
[15] Christopher Jones. Cartographic Name Placement with Prolog. IEEE Computer Graphics Applications, 9(5): 36-47, 1989.
[16] David S.Johnson, Umit Basoglu. The Use of Artificial Intelligence in the Automated Placement of Cartographic Names. Proceedings of Auto-Carto9, 1989.
[17] ESRI. Maplex—Automated Text Placement and Cartographic Design Software. http://www.esri.com/software/maplex/,2005.
[18] Evermap. EverName—Cartographic Label Placement Software for Maplnfo Professional. http://www.evermap.com/evername.htm,2005.
[19] Eduard Imhof. Positioning Names on Maps. The American Cartographer, 2(2): 128-144, 1975.
[20] Eduard Imhof. Die Anordnung der Namen in der Karte. International Yearbook of Cartography, 2: 93-129, 1962.
[21] G.E.Langran and T.K.Poiker. Integration of Name Selection and Name Placement. In Proceedings of the Second International Symposium on Spatial Data Handling: 50-64, 1986.
[22] Georges Alinhac. Cartographic Theorique et Technique, chapter IV. Institute Geographique National, Paris, 1962.
[23] Herbert Freeman. Label-EZTM—Software for Automated Cartographic Text Placement. White Paper of MapText Inc, 2004.
[24] Itzhak Pinto and Herbert Freeman. The Feedback Approach to Cartographic Area Text Placement. In Advances in Structural and Syntactical Pattern Recognition, A. Rosenfeld, P. Perner, and P. Wang, eds. Springer, Berlin, p: 341-50, 1996.
[25] Jon Christensen, Joe Marks, and Stuart Shieber. Labeling Point Features on Maps and Diagrams. Technical Report TR-25-92, Harvard CS, 1992.
[26] Jon Christensen, Joe Marks, and Stuart Shieber. Placing Text Labels on Maps and Diagrams. Graphics Gems Ⅳ, Academic Press: Cambridge, MA, 1994.
[27] Jon Christensen and Joe Marks. An Empirical Study of Algorithms for Point-Feature Label Placement. ACM Transactions on Graphics, 14(3): 203-232, 1995.
[28] Jon Christensen and Christopher B. Jones. Conflict Reduction in Map Generalization Using Iterative Improvement. Geoinformatica, 2(4), 1998.
[29] John Ahn and Herbert Freeman. AUTONAP——An Expert System for Automatic Map Name Placement. In Proceedings International Symposium on Spatial Data Handling, pages 544-569, 1984.
[30] Karla Hoffman and M. Padberg, Lp-Based Combinatorial Problem Solving. Annals of Operations Research 4:145-194, 1986.
[31] Lee R.Ebinger and Ann M.Goulette. Automated Names Placement in a Non-interactive Enviroment. Proceedings of Auto-Carto 9, 1989.
[32] MapText. MapText,Inc——The Leader in Automated Cartographic Text Placement. http://www.maptext.com/,2005.
[33] Mike Preu β. Solving Map Labeling Problems by Means of Evolution Strategies. Master's thesis, Fachbereich Informatik, University Dortmund, February 1998.
[34] Missae Yamamoto, Gilberto Camara and Luiz Antonio Nogueira Lorena. Tabu Search Heuristic for Point-Feature Cartographic Label Placement. GeoInformatica 6:1, 77-90, 2002.
[35] Pinhas Yoeli. The Logic of Automated Map Lettering. The Cartographic Journal, 9: 99-108, 1972.
[36] Shawn Edmondson, Jon Christensen, Joe Marks, and Stuart Shieber. A General Cartographic Labeling Algorithm. Cartographica, 33(4): 13-23, 1997.
[37] Stephen A.Hirsch. An Algorithm for Automatic Name Placement around Point Data. The American Cartographer, 9(1): 5-17, 1982.
[38] Steven van Dijk. Genetic Algorithms for Map Labeling. Ph.D. thesis, page: 9-10, 2001.
[39] Steven van Dijk, Marc van Kreveld, Tycho Strijk, Alexander Wolff. Towards an Evaluation of Quality for Names Placement Methods. International Journal of Geographical Information Science 16 (7): 641-661, 2002.
[40] Steven Zoraster. Integer Programming Applied to the Map Label Placement Problem. Cartogrphica, 23(3): 16-27, 1986.
[41] Tycho Strijk, Marc van Kreveld. Practical Extensions of Point Labeling in the Slider Model. Proceedings of the Seventh ACM International Symposium on Advances in Geographic Information Systems, page: 47-52, November 02-06, 1999.
[2] 张力果、赵淑梅编著,1983,地图学,高等教育出版社。
[3] 邬伦、刘瑜、张晶等,1991,地理信息系统原理、方法和应用,科学出版社。
[4] 姜美鑫、徐庆荣,1981,地形图绘制,测绘出版社。
[5] 尹贡白、王家耀、田德森、黄采芝编著,1991,地图概论,北京,测绘出版社。
[6] 王凌,2001,智能优化算法及其应用(第二章:模拟退火算法),清华大学出版社&施普林格出版社。
[7] 郭庆胜、任晓燕编制,2003,智能化地理信息处理,武汉大学出版社。
[8] 陈军,2002,Voronoi动态空间数据模型,北京,测绘出版社。
[9] 周培德,2000,计算几何——算法分析与设计,北京,清华大学出版社。
[10] 樊红,2001,地图注记自动配置的研究,博士学位论文。
[11] 罗广祥,2003,支持地图注记配置的数据模型与计算几何方法研究,博士学位论文。
[12] Alexander Wolff, Lars knipping, Marc van Kreveld, Tycho Strijk, and Pankaj K. Agarwal. A Simple and Efficient Algorithm for High-quality Line Labeling. GIS Research UK 7th Annual Conference: 146-150, 1999.
[13] Bernard Chazelle. Application Challenges to Computational Geometry. The Computational Geometry Impact Task Force Report, 1996.
[14] Borden D.Dent. Cartography, chapter 14. Wm.C.Brown Publishers, 1996.
[15] Christopher Jones. Cartographic Name Placement with Prolog. IEEE Computer Graphics Applications, 9(5): 36-47, 1989.
[16] David S.Johnson, Umit Basoglu. The Use of Artificial Intelligence in the Automated Placement of Cartographic Names. Proceedings of Auto-Carto9, 1989.
[17] ESRI. Maplex—Automated Text Placement and Cartographic Design Software. http://www.esri.com/software/maplex/,2005.
[18] Evermap. EverName—Cartographic Label Placement Software for Maplnfo Professional. http://www.evermap.com/evername.htm,2005.
[19] Eduard Imhof. Positioning Names on Maps. The American Cartographer, 2(2): 128-144, 1975.
[20] Eduard Imhof. Die Anordnung der Namen in der Karte. International Yearbook of Cartography, 2: 93-129, 1962.
[21] G.E.Langran and T.K.Poiker. Integration of Name Selection and Name Placement. In Proceedings of the Second International Symposium on Spatial Data Handling: 50-64, 1986.
[22] Georges Alinhac. Cartographic Theorique et Technique, chapter IV. Institute Geographique National, Paris, 1962.
[23] Herbert Freeman. Label-EZTM—Software for Automated Cartographic Text Placement. White Paper of MapText Inc, 2004.
[24] Itzhak Pinto and Herbert Freeman. The Feedback Approach to Cartographic Area Text Placement. In Advances in Structural and Syntactical Pattern Recognition, A. Rosenfeld, P. Perner, and P. Wang, eds. Springer, Berlin, p: 341-50, 1996.
[25] Jon Christensen, Joe Marks, and Stuart Shieber. Labeling Point Features on Maps and Diagrams. Technical Report TR-25-92, Harvard CS, 1992.
[26] Jon Christensen, Joe Marks, and Stuart Shieber. Placing Text Labels on Maps and Diagrams. Graphics Gems Ⅳ, Academic Press: Cambridge, MA, 1994.
[27] Jon Christensen and Joe Marks. An Empirical Study of Algorithms for Point-Feature Label Placement. ACM Transactions on Graphics, 14(3): 203-232, 1995.
[28] Jon Christensen and Christopher B. Jones. Conflict Reduction in Map Generalization Using Iterative Improvement. Geoinformatica, 2(4), 1998.
[29] John Ahn and Herbert Freeman. AUTONAP——An Expert System for Automatic Map Name Placement. In Proceedings International Symposium on Spatial Data Handling, pages 544-569, 1984.
[30] Karla Hoffman and M. Padberg, Lp-Based Combinatorial Problem Solving. Annals of Operations Research 4:145-194, 1986.
[31] Lee R.Ebinger and Ann M.Goulette. Automated Names Placement in a Non-interactive Enviroment. Proceedings of Auto-Carto 9, 1989.
[32] MapText. MapText,Inc——The Leader in Automated Cartographic Text Placement. http://www.maptext.com/,2005.
[33] Mike Preu β. Solving Map Labeling Problems by Means of Evolution Strategies. Master's thesis, Fachbereich Informatik, University Dortmund, February 1998.
[34] Missae Yamamoto, Gilberto Camara and Luiz Antonio Nogueira Lorena. Tabu Search Heuristic for Point-Feature Cartographic Label Placement. GeoInformatica 6:1, 77-90, 2002.
[35] Pinhas Yoeli. The Logic of Automated Map Lettering. The Cartographic Journal, 9: 99-108, 1972.
[36] Shawn Edmondson, Jon Christensen, Joe Marks, and Stuart Shieber. A General Cartographic Labeling Algorithm. Cartographica, 33(4): 13-23, 1997.
[37] Stephen A.Hirsch. An Algorithm for Automatic Name Placement around Point Data. The American Cartographer, 9(1): 5-17, 1982.
[38] Steven van Dijk. Genetic Algorithms for Map Labeling. Ph.D. thesis, page: 9-10, 2001.
[39] Steven van Dijk, Marc van Kreveld, Tycho Strijk, Alexander Wolff. Towards an Evaluation of Quality for Names Placement Methods. International Journal of Geographical Information Science 16 (7): 641-661, 2002.
[40] Steven Zoraster. Integer Programming Applied to the Map Label Placement Problem. Cartogrphica, 23(3): 16-27, 1986.
[41] Tycho Strijk, Marc van Kreveld. Practical Extensions of Point Labeling in the Slider Model. Proceedings of the Seventh ACM International Symposium on Advances in Geographic Information Systems, page: 47-52, November 02-06, 1999.