一种利用改进的扫描线算法计算拓扑关系的方法
|
摘要
针对以往拓扑关系计算方法的缺陷,提出一种利用改进的扫描线算法计算矢量数据拓扑关系的算法(TCBSL)。该算法以平面扫描转换法的思想为核心,通过改进扫描线算法结构,并引入拓扑关系判别参数,实现了较为高效地计算矢量数据空间实体之间的拓扑关系。此外,以该算法思想为依据,利用eclipse构建了矢量数据拓扑关系计算模型,并利用该模型对深圳市OSM矢量数据进行实验。实验显示,该算法可以较为正确地计算点线、点面、线线、线面及面面之间的拓扑关系,且效率较高,易于计算机系统的实现。
Aiming at the drawbacks of the former topology relation calculation methods, an vector data topology relation calculation algorithm(TCBSL) is proposed based on the improved scan line algorithm. The plane transformation scanning method is taken as a core method in TCBSL, the topology relation between spatial entities of vector data can be calculated efficiently through the improved structure of scan line algorithm and the introduced discriminant parameters of topology relation. Besides, a vector data topology relation calculation model based on TCBSL is established utilizing eclipse as the platform, and an experiment is carried out using OSM vector data of Shenzhen. The result shows the algorithm can calculate the topology relation of point-line, point-area, line-line, line-area and area-area entities comparatively correctly and efficiently, moreover, it is easy for computer system to realize.
Aiming at the drawbacks of the former topology relation calculation methods, an vector data topology relation calculation algorithm(TCBSL) is proposed based on the improved scan line algorithm. The plane transformation scanning method is taken as a core method in TCBSL, the topology relation between spatial entities of vector data can be calculated efficiently through the improved structure of scan line algorithm and the introduced discriminant parameters of topology relation. Besides, a vector data topology relation calculation model based on TCBSL is established utilizing eclipse as the platform, and an experiment is carried out using OSM vector data of Shenzhen. The result shows the algorithm can calculate the topology relation of point-line, point-area, line-line, line-area and area-area entities comparatively correctly and efficiently, moreover, it is easy for computer system to realize.
引文
[1] 崔铁军.地理空间分析原理[M].北京:科学出版社,2016:3-5;41-46.CUI T J.The principle of geospatial analysis[M].Beijing:Science Press,2016:3-5;41-46.
[2] 何广静,张新长,欧佳斌,等.基于直线段相交特征识别的线线空间关系计算方法[J].测绘学报,2015,44(S1):166-170.HE G J,ZHANG X C,OU J B,et al.A calculation method of space lines’ relationship based on recognition of linear segment intersection feature[J].Acta Geodaetica et Cartographica Sinica,2015,44(S1):166-170.
[3] 沈敬伟,温永宁,闾国年,等.体/体拓扑关系计算研究[J].测绘科学,2012,37(4):120-122.SHEN J W,WEN Y N,LYU G N,et al.Calculation of topological relationships between bodies[J].Science of Surveying and Mapping,2012,37(4):120-122.
[4] CHEN J,LI C M,LI Z L,et al.A Voronoi-based 9-intersection model for spatial relations[J].International Journal of Geographical Information Systems,2001,15(3):20.
[5] 牛继强,徐丰.空间数据多尺度表达中空间关系的统一表达模型[J].测绘科学技术学报,2013,30(2):182-186.NIU J Q,XU F.Integrated representation of spatial relations in multi-scale representation of spatial data[J].Journal of Geomatics Science and Technology,2013,30(2):182-186.
[6] 倪建华.拓扑关系计算方法研究与实现[D].长沙:中南大学,2009:1-2.NI J H.Research and implementation of computation of topological relationships[D].Changsha:Central South University,2009:1-2.
[7] 鲁磊,张红波.空间拓扑查询研究与实现[J].测绘通报,2012(S1):588-592.LU L,ZHANG H B.Research and implementation of spatial topology query[J].Bulletin of Surveying and Mapping,2012(S1):588-592.
[8] 吴明光,崔登吉,闾国年.一种高效的拓扑关系计算方法:CN,CN105468693 A[P].2019-01-18.WU M G,CUI D J,LYU G N.An efficient method of topological relation calculation:CN,CN105468693 A[P].2019-01-18.
[9] 董孟秋.基于模糊Voronoi图的面向对象空间关系研究[D].桂林:桂林理工大学,2014:1-3.DONG M Q.Research in object-oriented spatial relations based on fuzzy theory Voronoi diagram[D].Guilin:Guilin University of Technology,2014:1-3.
[10] 徐胜攀,刘正军,左志权,等.一种改进的活性边表区域填充算法[J].计算机工程与应用,2014,50(17):178-181.XU S P,LIU Z J,ZUO Z Q,et al.Improved active-edge-table area filling algorithm[J].Computer Engineering and Applications,2014,50(17):178-181.
[11] 任继成,刘慎权.区域填充扫描线算法的改进[J].计算机辅助设计与图形学学报,1998(6):481-486.REN J C,LIU S Q.Improvement of area filling scanline algorithm[J].Journal of Computer-Aided Design and Computer Graphics,1998(6):481-486.
[2] 何广静,张新长,欧佳斌,等.基于直线段相交特征识别的线线空间关系计算方法[J].测绘学报,2015,44(S1):166-170.HE G J,ZHANG X C,OU J B,et al.A calculation method of space lines’ relationship based on recognition of linear segment intersection feature[J].Acta Geodaetica et Cartographica Sinica,2015,44(S1):166-170.
[3] 沈敬伟,温永宁,闾国年,等.体/体拓扑关系计算研究[J].测绘科学,2012,37(4):120-122.SHEN J W,WEN Y N,LYU G N,et al.Calculation of topological relationships between bodies[J].Science of Surveying and Mapping,2012,37(4):120-122.
[4] CHEN J,LI C M,LI Z L,et al.A Voronoi-based 9-intersection model for spatial relations[J].International Journal of Geographical Information Systems,2001,15(3):20.
[5] 牛继强,徐丰.空间数据多尺度表达中空间关系的统一表达模型[J].测绘科学技术学报,2013,30(2):182-186.NIU J Q,XU F.Integrated representation of spatial relations in multi-scale representation of spatial data[J].Journal of Geomatics Science and Technology,2013,30(2):182-186.
[6] 倪建华.拓扑关系计算方法研究与实现[D].长沙:中南大学,2009:1-2.NI J H.Research and implementation of computation of topological relationships[D].Changsha:Central South University,2009:1-2.
[7] 鲁磊,张红波.空间拓扑查询研究与实现[J].测绘通报,2012(S1):588-592.LU L,ZHANG H B.Research and implementation of spatial topology query[J].Bulletin of Surveying and Mapping,2012(S1):588-592.
[8] 吴明光,崔登吉,闾国年.一种高效的拓扑关系计算方法:CN,CN105468693 A[P].2019-01-18.WU M G,CUI D J,LYU G N.An efficient method of topological relation calculation:CN,CN105468693 A[P].2019-01-18.
[9] 董孟秋.基于模糊Voronoi图的面向对象空间关系研究[D].桂林:桂林理工大学,2014:1-3.DONG M Q.Research in object-oriented spatial relations based on fuzzy theory Voronoi diagram[D].Guilin:Guilin University of Technology,2014:1-3.
[10] 徐胜攀,刘正军,左志权,等.一种改进的活性边表区域填充算法[J].计算机工程与应用,2014,50(17):178-181.XU S P,LIU Z J,ZUO Z Q,et al.Improved active-edge-table area filling algorithm[J].Computer Engineering and Applications,2014,50(17):178-181.
[11] 任继成,刘慎权.区域填充扫描线算法的改进[J].计算机辅助设计与图形学学报,1998(6):481-486.REN J C,LIU S Q.Improvement of area filling scanline algorithm[J].Journal of Computer-Aided Design and Computer Graphics,1998(6):481-486.