地学制图综合中多边形对象的合并算法研究与应用
|
摘要
随着地学图件的数字化及地学数据库的广泛建立，经常会从大比例尺数据生产小比例尺数据，因此自动制图综合成为了研究的前沿和热点问题。多边形图件是应用中非常普遍的数据，如地质图、土壤类型图、地籍图，随着图件比例尺的缩小，多边形之间会产生图形显示方面的冲突，要通过相应的操作消除这些冲突，最常见的操作之一是多边形的合并。但是目前的多边形合并算法存在许多局限和不足。
本文提出了基于约束Delaunay三角网剖分的多边形合并改进模型。该模型主要包括四个部分：多边形的一次聚类分析、约束Delaunay三角网剖分、多边形的邻近分析和多边形的合并。首先通过对图件的第一层次聚类，将多边形目标划分成许多独立的小区域；然后分别对这些区域进行约束Delaunay三角网剖分，将每个区域划分成简单三角形连接的区域；接着基于连接三角形，对多边形进行邻近分析即第二层次的聚类，建立冲突的多边形组；最后将冲突的多边形组和归属于该组的β类三角形和)，类三角形进行合并。
基于二次开发控件MapObjiects和ArcSDE C-API函数库，在Visual C++6.0环境下开发了多边形自动合并系统，实现了多边形合并的改进模型，并针对地质图和地籍图进行了应用，研究表明，本文提出的改进模型在多边形合并方面，取得了比较好的效果。
The digitalization of geo-maps and the broad establishment of geo-databases bring along a frequent need to produce small scale maps from large ones. As a result, automatic cartographic generalization has become the frontier and the main focus in this research field. Polygonal maps are a common data type in applications, such as geological maps, soil maps, and cadastral maps. As the map scale reduces, graphic conflicts raise between polygons. Operations have to been adopted to solve these conflicts, and aggregation is the most in common use. However, there are many shortcomings of current algorithms for polygon aggregation.
In this thesis, an improved model for polygon aggregation based on constrained delaunay triangulation is put forward. The model mainly includes four parts: first clustering analysis of polygons, constrained delaunay triangulation, proximity analysis of polygons, and aggregation of polygons. First, a clustering analysis with map data is done in order to divide whole data into several parts. Second, a constrained delaunay triangulation is constructed for each part. Third, proximity analysis (second clustering analysis) is done to classify polygons with conflicts. At last, polygons with conflicts,βtriangle andγtriangle belong to them are aggregated.
An automatic polygon aggregation system for the improved model is developed based on MapObjects and ArcSDE C-API in the environment of Visual C++ 6.0. It is then tried out in a geological map and a cadastral map. Applications show the advantage of this improved model for polygon aggregation.
本文提出了基于约束Delaunay三角网剖分的多边形合并改进模型。该模型主要包括四个部分：多边形的一次聚类分析、约束Delaunay三角网剖分、多边形的邻近分析和多边形的合并。首先通过对图件的第一层次聚类，将多边形目标划分成许多独立的小区域；然后分别对这些区域进行约束Delaunay三角网剖分，将每个区域划分成简单三角形连接的区域；接着基于连接三角形，对多边形进行邻近分析即第二层次的聚类，建立冲突的多边形组；最后将冲突的多边形组和归属于该组的β类三角形和)，类三角形进行合并。
基于二次开发控件MapObjiects和ArcSDE C-API函数库，在Visual C++6.0环境下开发了多边形自动合并系统，实现了多边形合并的改进模型，并针对地质图和地籍图进行了应用，研究表明，本文提出的改进模型在多边形合并方面，取得了比较好的效果。
The digitalization of geo-maps and the broad establishment of geo-databases bring along a frequent need to produce small scale maps from large ones. As a result, automatic cartographic generalization has become the frontier and the main focus in this research field. Polygonal maps are a common data type in applications, such as geological maps, soil maps, and cadastral maps. As the map scale reduces, graphic conflicts raise between polygons. Operations have to been adopted to solve these conflicts, and aggregation is the most in common use. However, there are many shortcomings of current algorithms for polygon aggregation.
In this thesis, an improved model for polygon aggregation based on constrained delaunay triangulation is put forward. The model mainly includes four parts: first clustering analysis of polygons, constrained delaunay triangulation, proximity analysis of polygons, and aggregation of polygons. First, a clustering analysis with map data is done in order to divide whole data into several parts. Second, a constrained delaunay triangulation is constructed for each part. Third, proximity analysis (second clustering analysis) is done to classify polygons with conflicts. At last, polygons with conflicts,βtriangle andγtriangle belong to them are aggregated.
An automatic polygon aggregation system for the improved model is developed based on MapObjects and ArcSDE C-API in the environment of Visual C++ 6.0. It is then tried out in a geological map and a cadastral map. Applications show the advantage of this improved model for polygon aggregation.
引文
艾廷华，刘耀林．土地利用数据综合中的聚合与融合[J]．武汉大学学报·信息科学版，2002，27(5)：486-492．
陈继宁，张晓东．Oracle Spatial和ArcSDE的应用比较研究[J]．遥感信息，2005，(5)：60-63．
邓曙光，刘刚，邹帆．约束数据域Delaunay算法详述及进展[J]．沈阳航空工业学院学报，2005．10，22(5)：79-81．
杜培军，程朋根．计算机地图制图原理与方法[M]．徐州：中国矿业大学出版社，2006．
弗·特普费尔．制图综合(江安宁译)[M]．北京：测绘出版社，1982．
韩鹏．地理信息系统开发—MapObjects方法[M]．武汉：武汉大学出版社，2004．
焦健，曾琪明．地图学[M]．北京：北京大学出版社，2005．
李志林，朱庆．数字高程模型[M]．武汉：武汉大学出版社，2001．
刘少华，程朋根，史文中．CDT生成算法研究[J]．测绘通报，2004，(3)：4-7．
刘学军，龚健雅．约束数据域的Delaunay三角剖分与修改算法[J]．测绘学报，2001，30(1)：82-88．
普雷帕拉塔 F P，沙莫斯M I．计算几何导论[M]．北京：科学出版社，1990．
钱海忠，刘颖，张琳琳，等．基于圆特征的地图要素自动综合算法研究[J]．海洋测绘，2005a，25(1)：14-17．
钱海忠，武芳，谭笑，等．基于ABTM的城市建筑物合并算法[J]．中国图象图形学报，2005b，10(10)：1224-1233．
任振娜，李斌兵，周浩，等．一次性生成CDT算法的编程与实现[J]．测绘工程，2006，15(1)：54-58．
史佳顺，朱赞，黄继风．一种建筑物多边形合并、化简与优化的自动方案[J]．计算机工程，2003，29(1)：204-205．
王家耀，孙群，王光霞，等．地图学原理与方法[M]．北京：科学出版社，2006．
武芳，邓红艳．基于遗传算法的线要素自动化简模型[J]．测绘学报，2003，32(4)：349-355．
吴宇晓，张登荣．生成Delaunay三角网的快速合成算法[J]．浙江大学学报(理学版)，2004，31(3)：343-348．
熊丽华，杨峰．基于ArcSDE的空间数据库技术的应用研究[J]．计算机应用，2004，24(3)：90-91．
应申，李霖，王明常，等．计算几何在制图综合中的应用[J]．测绘科学，2005，30(3)：64-66．
张晶，周烨，刘瑜．SDS模型化简合并多边形的一个改进算法研究[J]．中国图象图形学报，2006，11(7)：1010-1016．
Alessandro C. Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D]. Zurich:Zurich University, 2003.
Bader M, Weibel R. Detecting and resolving size and proximity conflicts in the generalization of polygonal maps[C]. 18th International Cartographic Conference, Stockholm, 1997.
Basaraner M, Selck M. An attempt to automated generalization of buildings and settlement areas in topographic maps[C]. ISPRS Commission Ⅳ, WG Ⅳ/3, Istanbul, Turkey, 2004.
Brassel K E, Weibel R. A review and conceptual framework of automated map generalization[J]. International Journal of Geographical Information system, 1988, 2 (3): 229-244.
Dan Lee. Geographic and cartographic contexts in generalization[C]. Workshop on generalisation and multiple representation, ICA, commission on map generalisation, Leicester, United Kingdom, August, 2004.
Jones C B, Ware J M, Eynon C D. Triangulated spatial models and neighbourhood search:an experimental comparison with quadtrees[J]. The Visual Computer, 1999, 15(5):235-248.
Joseph O'Rourke. Computational geometry in C (Second Edition) [M]. 机械工业出版社,2005.
Martin G. Optimization techniques for polygon generalization[C]. ICA-Workshop on Progress in Automated Map Generalization, Beijing(China), 2001.
Martin G. Automated polygon generalization in a multi agent system[D]. Zurich:Zurich University, 2003.
Peter B, Weibel R. Using vector and raster-based techniques in categorical map generalization[C]. Third ICA Workshop on Progress in Automated Map Generalization, Ottawa, 1999, 12-14.
Ruas A. Multiple paradigms for automating map generalization:geometry, topology, hierarchical partitioning & local triangulation[C].ACSM/ASPRS Annual Convension and Exposition, 1995, 4:69-78.
Ruas A, Plazaner C. Strategies for automated generalization[M]. Proceedings of SDH, 1996, 6A1-15.
Rusak M E, Castner H W. Horton's ordering scheme and the generalisation of river networks[J]. The Cartographic Journal, 1990, 27: 104-112.
Thompson R C, Richardson D E. A graph theory approach to road network generalization[C]. Proceedings of the 17thlCA, Barcelona, 1995, 1871-1880.
Ware J M, Jones C B, Thomas N. Automated map generalization with multiple operators: a simulated annealing approach[J]. Geographical Information Science, 2003, 17(8): 743-769.
Wilson I D, Ware J M, Ware J A. A genetic algorithm approach to cartographic map generalization[J]. Computers in Industry(Elsevier Science), 2003, 52(3): 291-304.
陈继宁，张晓东．Oracle Spatial和ArcSDE的应用比较研究[J]．遥感信息，2005，(5)：60-63．
邓曙光，刘刚，邹帆．约束数据域Delaunay算法详述及进展[J]．沈阳航空工业学院学报，2005．10，22(5)：79-81．
杜培军，程朋根．计算机地图制图原理与方法[M]．徐州：中国矿业大学出版社，2006．
弗·特普费尔．制图综合(江安宁译)[M]．北京：测绘出版社，1982．
韩鹏．地理信息系统开发—MapObjects方法[M]．武汉：武汉大学出版社，2004．
焦健，曾琪明．地图学[M]．北京：北京大学出版社，2005．
李志林，朱庆．数字高程模型[M]．武汉：武汉大学出版社，2001．
刘少华，程朋根，史文中．CDT生成算法研究[J]．测绘通报，2004，(3)：4-7．
刘学军，龚健雅．约束数据域的Delaunay三角剖分与修改算法[J]．测绘学报，2001，30(1)：82-88．
普雷帕拉塔 F P，沙莫斯M I．计算几何导论[M]．北京：科学出版社，1990．
钱海忠，刘颖，张琳琳，等．基于圆特征的地图要素自动综合算法研究[J]．海洋测绘，2005a，25(1)：14-17．
钱海忠，武芳，谭笑，等．基于ABTM的城市建筑物合并算法[J]．中国图象图形学报，2005b，10(10)：1224-1233．
任振娜，李斌兵，周浩，等．一次性生成CDT算法的编程与实现[J]．测绘工程，2006，15(1)：54-58．
史佳顺，朱赞，黄继风．一种建筑物多边形合并、化简与优化的自动方案[J]．计算机工程，2003，29(1)：204-205．
王家耀，孙群，王光霞，等．地图学原理与方法[M]．北京：科学出版社，2006．
武芳，邓红艳．基于遗传算法的线要素自动化简模型[J]．测绘学报，2003，32(4)：349-355．
吴宇晓，张登荣．生成Delaunay三角网的快速合成算法[J]．浙江大学学报(理学版)，2004，31(3)：343-348．
熊丽华，杨峰．基于ArcSDE的空间数据库技术的应用研究[J]．计算机应用，2004，24(3)：90-91．
应申，李霖，王明常，等．计算几何在制图综合中的应用[J]．测绘科学，2005，30(3)：64-66．
张晶，周烨，刘瑜．SDS模型化简合并多边形的一个改进算法研究[J]．中国图象图形学报，2006，11(7)：1010-1016．
Alessandro C. Integration of cartographic generalization and multi-scale databases for enhanced web mapping[D]. Zurich:Zurich University, 2003.
Bader M, Weibel R. Detecting and resolving size and proximity conflicts in the generalization of polygonal maps[C]. 18th International Cartographic Conference, Stockholm, 1997.
Basaraner M, Selck M. An attempt to automated generalization of buildings and settlement areas in topographic maps[C]. ISPRS Commission Ⅳ, WG Ⅳ/3, Istanbul, Turkey, 2004.
Brassel K E, Weibel R. A review and conceptual framework of automated map generalization[J]. International Journal of Geographical Information system, 1988, 2 (3): 229-244.
Dan Lee. Geographic and cartographic contexts in generalization[C]. Workshop on generalisation and multiple representation, ICA, commission on map generalisation, Leicester, United Kingdom, August, 2004.
Jones C B, Ware J M, Eynon C D. Triangulated spatial models and neighbourhood search:an experimental comparison with quadtrees[J]. The Visual Computer, 1999, 15(5):235-248.
Joseph O'Rourke. Computational geometry in C (Second Edition) [M]. 机械工业出版社,2005.
Martin G. Optimization techniques for polygon generalization[C]. ICA-Workshop on Progress in Automated Map Generalization, Beijing(China), 2001.
Martin G. Automated polygon generalization in a multi agent system[D]. Zurich:Zurich University, 2003.
Peter B, Weibel R. Using vector and raster-based techniques in categorical map generalization[C]. Third ICA Workshop on Progress in Automated Map Generalization, Ottawa, 1999, 12-14.
Ruas A. Multiple paradigms for automating map generalization:geometry, topology, hierarchical partitioning & local triangulation[C].ACSM/ASPRS Annual Convension and Exposition, 1995, 4:69-78.
Ruas A, Plazaner C. Strategies for automated generalization[M]. Proceedings of SDH, 1996, 6A1-15.
Rusak M E, Castner H W. Horton's ordering scheme and the generalisation of river networks[J]. The Cartographic Journal, 1990, 27: 104-112.
Thompson R C, Richardson D E. A graph theory approach to road network generalization[C]. Proceedings of the 17thlCA, Barcelona, 1995, 1871-1880.
Ware J M, Jones C B, Thomas N. Automated map generalization with multiple operators: a simulated annealing approach[J]. Geographical Information Science, 2003, 17(8): 743-769.
Wilson I D, Ware J M, Ware J A. A genetic algorithm approach to cartographic map generalization[J]. Computers in Industry(Elsevier Science), 2003, 52(3): 291-304.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |