Position Clustering for Polygon Object under Dual-constrains

doi:10.11947/j.AGCS.2016.20150491

Abstract

Abstract:

It is a vital research direction for spatial clustering to recognize polygon cluster, but due to the dual-constrains by geometric information of polygons and obstacles, the position similarity of polygon is difficult to calculate accurately and quickly.A polygon clustering algorithm under dual-constrains is proposed by extending the algorithm of multi-scale spatial clustering, and constructing an intensity function to express position aggregation between object and its adjacent object. For further discuss, it takes the same thresholds of intensity function in adjacent scales as convergence condition. Simulated polygons and real data are chosen to perform clustering in experiments to verify the validity of our algorithm. Results show that without predefined parameters, this algorithm can identify variety polygon clusters with different densities, arbitrary shape, bridge and obstacle.

Key words: polygon, position clustering, Voronoi diagram, spatial obstacle, assessment index

CLC Number:

P208

YU Li, GAN Shu, YUAN Xiping, LI Jiatian. Position Clustering for Polygon Object under Dual-constrains[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(10): 1250-1259.

References

[1] 辜寄蓉, 陈先伟, 杨海龙. 城市功能区划分空间聚类算法研究[J]. 测绘科学, 2011, 36(5):65-67. GU Jirong, CHEN Xianwei, YANG Hailong. Spatial Clustering Algorithm on Urban Function Oriented Zone[J]. Science of Surveying and Mapping, 2011, 36(5):65-67.
[2] CAO Zechun, WANG Sujing, FORESTIER G, et al. Analyzing the Composition of Cities Using Spatial Clustering[C]//Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing. New York:ACM, 2013:14.
[3] STEINHAUER J H, WIESE T, FREKSA C, et al. Recognition of Abstract Regions in Cartographic Maps[M]//MONTELLO D R. Spatial Information Theory. Berlin Heidelberg:Springer, 2001:306-321.
[4] YAN Haowen, WEIBEL R, YANG Bisheng. A Multi-Parameter Approach to Automated Building Grouping and Generalization[J]. Geoinformatica, 2008, 12(1):73-89.
[5] 邓敏, 孙前虎, 文小岳, 等. 建筑物层次空间聚类方法研究[J]. 计算机工程与应用, 2011, 47(28):120-123. DENG Min, SUN Qianhu, WEN Xiaoyue, et al. Hierarchical Spatial Clustering of Buildings[J]. Computer Engineering and Applications, 2011, 47(28):120-123.
[6] 马利邦, 郭晓东, 张启媛. 甘谷县乡村聚落时空布局特征及格局优化[J]. 农业工程学报, 2012, 28(13):217-225. MA Libang, GUO Xiaodong, ZHANG Qiyuan. Spatio-Temporal Distribution and Optimization of Rural Settlements in Gangu County of Loess Hilly Area[J]. Transactions of the Chinese Society of Agricultural Engineering, 2012, 28(13):217-225.
[7] 艾廷华, 郭仁忠. 基于格式塔识别原则挖掘空间分布模式[J]. 测绘学报, 2007, 36(3):302-308. DOI:10.3321/j.issn:1001-1595.2007.03.011. AI Tinghua, GUO Renzhong. Polygon Cluster Pattern Mining based on Gestalt Principles[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(3):302-308. DOI:10.3321/j.issn:1001-1595.2007.03.011.
[8] 闫浩文, 应申, 李霖. 多因子影响的地图居民地自动聚群与综合研究[J]. 武汉大学学报(信息科学版), 2008, 33(1):51-54. YAN Haowen, YING Shen, LI Lin. An Approach for Automated Building Grouping and Generalization Considering Multiple Parameters[J]. Geomatics and Information Science of Wuhan University, 2008, 33(1):51-54.
[9] 邓敏, 刘启亮, 李光强, 等. 空间聚类分析及应用[M]. 北京:科学出版社, 2011. DENG Min, LIU Qiliang, LI Guangqiang, et al. Analysis and Application of Spatial Clustering[M]. Beijing:Science Press, 2011.
[10] BARRAULT M, REGNAULD N, DUCHENE C, et al. Integrating Multi-agent, Object-oriented, and Algorithmic Techniques for Improved Automated Map Generalization[C]//Proceedings of 20th International Cartographic Conference. Beijing:Publishing House of Surveying and Mapping, 2001:2110-2116.
[11] 杨春成, 何列松, 谢鹏, 等. 顾及距离与形状相似性的面状地理实体聚类[J]. 武汉大学学报(信息科学版), 2009, 34(3):335-338. YANG Chuncheng, HE Liesong, XIE Peng, et al. Clustering Analysis of Geographical Area Entities Considering Distance and Shape Similarity[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3):335-338.
[12] ZHANG Xiang, AI Tinghua, STOTER J S, et al. Building Pattern Recognition in Topographic Data:Examples on Collinear and Curvilinear Alignments[J]. Geoinformatica, 2013, 17(1):1-33.
[13] ALT H, BEHRENDS B, BLÖMER J. Approximate Matching of Polygonal Shapes[J]. Annals of Mathematics and Artificial Intelligence, 1995, 13(3-4):251-265.
[14] WANG Sujing, CHEN Chunsheng, RINSURONGKAWONG V, et al. A Polygon-based Methodology for Mining Related Spatial Datasets[C]//Proceedings of the 1st ACM SIGSPATIAL International Workshop on Data Mining for Geoinformatics. New York:ACM, 2010:1-8.
[15] DAVIS E. Representations of Commonsense Knowledge[M]. San Mateo:Morgan Kaufmann, 1990.
[16] DENG Min, LI Zhilin, CHEN Xiaoyong. Extended Hausdorff Distance for Spatial Objects in GIS[J]. International Journal of Geographical Information Science, 2007, 21(4):459-475.
[17] JOSHI D, SAMAL A K, SOH L K. Density-based Clustering of Polygons[C]//Proceedings of the CIDM'09 IEEE Symposium on Computational Intelligence and Data Mining. Nashville, TN:IEEE, 2009:171-178.
[18] HUH Y, KIM J, LEE J, et al. Identification of Multi-Scale Corresponding Object-Set Pairs between Two Polygon Datasets with Hierarchical Co-Clustering[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2014, 88:60-68.
[19] 耿协鹏, 杜晓初, 胡鹏. 基于栅格距离变换的扩展对象空间聚类方法[J]. 测绘学报, 2009, 38(2):162-167, 174. DOI:10.3321/j.issn:1001-1595.2009.02.012. GENG Xiepeng, DU Xiaochu, HU Peng. Spatial Clustering Method Based on Raster Distance Transform for Extended Objects[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(2):162-167, 174. DOI:10.3321/j.issn:1001-1595.2009.02.012.
[20] HALKIDI M, VAZIRGIANNIS M. NPClu:An Approach for Clustering Spatially Extended Objects[J]. Intelligent Data Analysis, 2008, 12(6):587-606.
[21] SANDER J, ESTER M, KRIRGEL H P, et al. Density-based Clustering in Spatial Databases:The Algorithm GDBSCAN and Its Applications[J]. Data Mining and Knowledge Discovery, 1998, 2(2):169-194.
[22] 黎韶光, 周巨锁, 谢玉波, 等. 一种面向扩展空间对象的密度聚类算法[J]. 计算机工程与应用, 2011, 47(13):166-168. LI Shaoguang, ZHOU Jusuo, XIE Yubo, et al. Density-based Clustering Algorithm for Extended Spatial Objects[J]. Computer Engineering and Applications, 2011, 47(13):166-168.
[23] 张丽, 吉根林. 基于点面包含关系的GML空间聚类算法[J]. 小型微型计算机系统, 2010, 31(4):702-705. ZHANG Li, JI Genlin. Algorithm for Spatial Clustering in GML Data Based on Point-Region Spatial Inclusion Relation[J]. Journal of Chinese Computer Systems, 2010, 31(4):702-705.
[24] 余莉, 甘淑, 袁希平, 等. 综合线面特征分布的点目标多尺度聚类方法[J]. 测绘学报, 2015, 44(10):1152-1159. DOI:10.11947/j.AGCS.2015.20150136. YU Li, GAN Shu, YUAN Xiping, et al. Multi-Scale Clustering of Points Synthetically Considering Lines and Polygons Distribution[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(10):1152-1159. DOI:10.11947/j.AGCS.2015.20150136.
[25] 王中辉, 闫浩文. 基于方向Voronoi图模型的群组目标空间方向关系计算[J]. 小型微型计算机系统, 2013, 38(5):584-588. WANG Zhonghui, YAN Haowen. Computation of Direction Relations between Object Groups Based on Direction Voronoi Diagram Model[J]. Geomatics and Information Science of Wuhan University, 2013, 38(5):584-588.
[26] TOBLER W R. A Computer Movie Simulating Urban Growth in the Detroit Region[J]. Economic Geography, 1970, 46(S1):234-240.
[27] 王新生, 刘纪远, 庄大方, 等. 基于GIS的任意发生元Voronoi图逼近方法[J]. 地理科学进展, 2004, 23(4):97-102. WANG Xinsheng, LIU Jiyuan, ZHUANG Dafang, et al. GIS-based Approximation Algorithm for Constructing Voronoi Diagrams with General Generators[J]. Progress in Geography, 2004, 23(4):97-102.
[28] 李佳田, 杨琪莉, 罗富丽, 等. 线/面Voronoi图的分解合并生成算法[J]. 武汉大学学报(信息科学版), 2015, 40(11):1545-1550. LI Jiatian, YANG Qili, LUO Fuli, et al. A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J]. Geomatics and Information Science of Wuhan University, 2015, 40(11):1545-1550.
[29] BERRY M J A, LINOFF G S. Data Mining Techniques:For Marketing, Sales, and Customer Support[M]. New York:John Wiley &Sons, 1997.
[30] 刘启亮, 邓敏, 石岩, 等. 一种基于多约束的空间聚类方法[J]. 测绘学报, 2011, 40(4):509-516. LIU Qiliang, DENG Min, SHI Yan, et al. A Novel Spatial Clustering Method Based on Multi-constraints[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4):509-516.