Point Group Generalization Method Based on Hierarchical Voronoi Diagram

doi:10.13485/j.cnki.11-2089.2014.0166

Abstract

Abstract: The importance of the point is described by distance weight and the clustering center point of a point group is obtained by modified k-means algorithm. Furthermore, the clustering center is taken as base to construct hierarchical weighted Voronoi diagram and hierarchical tree structure. Distribution scope, arrangement, and density of the group is taken as the measurement to construct the point generalization method based on hierarchical Voronoi diagram tree structure, thus ensuring the consistency in spatial morphology before and after. Combination with geological statistics calculation, this generalization method is estimated and optimized. Finally, the practicability and availability of this method is confirmed through concrete experiment.

Key words: point group generalization, weight, spatial clustering, hierarchical Voronoi diagram, tree structure

CLC Number:

P283

LI Jiatian, KANG Shun, LUO Fuli. Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(12): 1300-1306.

References

[1] MA Yongli. Cartography Course[M]. Nanjing: Nanjing University Press,2003. (马永立. 地图学教程[M]. 南京: 南京大学出版社, 2003.)
[2] YU Yanping, SHEN Jie, SHANG Zaiying. A Study on the Time Complexity of Point Cluster Selection and Simplification Algorithms[J]. Journal of Nanjing Normal University: Natural Science Edition, 2012, 35(1): 111-116. (于艳平,沈婕,尚在颖. 点群选取与化简算法时间复杂度研究[J]. 南京师范大学报: 自然科学版, 2012, 35(1): 111-116.)
[3] WANG Jiayao, DENG Hongyan. A Model of Cartographical Generalization Based on Genetic Algorithm[J]. Geomatics and Information Science of Wuhan University, 2005, 30(7): 565-569. (王家耀,邓红艳. 基于遗传算法的制图综合模型研究[J]. 武汉大学学报: 信息科学版, 2005, 30(7): 565-569.)
[4] QIAN Haizong, WU Fang, ZHANG Linlin, et al. Quality Assessment of Point Group Geometry Generalization with Polarization Transformation[J]. Acta Geodaetica et Cartographica Sinica, 2005, 34(4): 261-269. (钱海忠,武芳,张琳琳,等. 基于极化变换的点群综合几何质量评估[J]. 测绘学报,2005, 34(4): 261-269.)
[5] LU Yi, ZHAI Jingsheng, DU Jinghai, et al. Recognition, Measurement and Generalization for Point Cluster Features in Digital Nautical Chart[J]. Geomatics and Information Science of Wuhan University, 2001, 26(2): 133-139. (陆毅,翟京生,杜景海,等. 数字海图点群状特征的识别、量测与综合[J]. 武汉大学学报: 信息科学版,2001, 26(2): 133-139.)
[6] GUO Qingsheng. Structuralizing Point Features and Its's Application in Map Generalization[J]. Journal of the PLA Institute of Surveying and Mapping, 1999, 16(3): 210-213. (郭庆胜. 点状要素群的结构化及其在综合中的应用[J]. 解放军测绘学院学报,1999, 16(3): 210-213.)
[7] AI Tinghua, LIU Yaolin. A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181. (艾延华,刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2): 175-181.)
[8] ELENA D, MICHEL M D. Encyclopedia of Distance[M]. [S. l]: Luthaze Press, 2009.
[9] GUO Qingsheng, ZHENG Chunyan, HU Huake. Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 256-261. (郭庆胜,郑春燕,胡华科. 基于邻近图的点群层次聚类方法的研究[J]. 测绘学报, 2008, 37(2): 256-261.)
[10] DAVIES D L, BOULDIN D W. A Cluster Separation Measure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227.
[11] CHEN Jun. Voronoi-based Dynamic Spatial Data Model[M]. Beijing: Surveying and Mapping Press, 2002. (陈军. Voronoi动态空间数据模型[M]. 北京: 测绘出版社, 2002.)
[12] ZHAO Renliang. Voronoi Methods for Computing Spatial Relations in GIS[M]. Beijing: Surveying and Mapping Press, 2006. (赵仁亮. 基于Voronoi图的GIS空间关系计算[M]. 北京: 测绘出版社, 2006.)
[13] BALZER M, DEUSSEN O. Voronoi Treemaps[C]// IEEE Symposium on Information Visualization 2005: INFOVIS. New York: IEEE, 2005: 49-56.
[14] DONG P L. Generating and Updating Multiplicatively Weighted Voronoi Diagrams for Point, Line and Polygon Features in GIS[J]. Computers & Geosciences, 2008, 34(4): 411-421.
[15] AURENHAMMER F, EDELSBRUNNER H. An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane [J]. Pattern Recognition, 1984, 17(2): 251-257.
[16] LIU Tao, DU Qingyun, YAN Haowen. Spatial Similarity Assessment of Point Clusters[J]. Geomatics and Information Science of Wuhan University, 2011, 36(10): 1149-1153. (刘涛,杜清运,闫浩文. 空间点群目标相似度计算[J]. 武汉大学学报: 信息科学版, 2011, 36(10): 1149-1153.)
[17] BONAN L, FREDERICO F. TDD: A Comprehensive Model for Qualitative Spatial Similarity Assessment [J]. Spatial Cognition and Computation, 2006, 6(1): 31-62.
[18] CAI Y X, GUO Q S. Point Set Generalization Based on the Kohonet Net[J]. Geo-spatial Information Science, 2008, 11(3): 221-227.
[19] LI Yulong, ZHU Huahua. Automated Recognition of Point Cluster Scope with Voronoi Diagram[J]. Journal of Engineering Graphics, 2007, 28(3): 73-77. (李玉龙,朱华华. 应用Voronoi图的点群范围自动识别[J]. 工程图学学报, 2007, 28(3): 73-77.)
[20] PATRICIA F, RAY L, JOHN R. A Comparison of Geometric Approaches to Assessing Spatial Similarity for GIR [J]. International Journal of Geographical Information Science, 2008, 22(3): 337-360.