杜灵瑀, 贲进, 马秋禾, 王蕊, 李祝鑫. 基于弱对偶的平面三角形格网离散线转化生成算法[J]. 武汉大学学报 ( 信息科学版), 2020, 45(1): 105-110. DOI: 10.13203/j.whugis20180205
引用本文: 杜灵瑀, 贲进, 马秋禾, 王蕊, 李祝鑫. 基于弱对偶的平面三角形格网离散线转化生成算法[J]. 武汉大学学报 ( 信息科学版), 2020, 45(1): 105-110. DOI: 10.13203/j.whugis20180205
DU Lingyu, BEN Jin, MA Qiuhe, WANG Rui, LI Zhuxin. An Algorithm for Generating Discrete Line Transformation of Planar Triangular Grid Based on Weak Duality[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 105-110. DOI: 10.13203/j.whugis20180205
Citation: DU Lingyu, BEN Jin, MA Qiuhe, WANG Rui, LI Zhuxin. An Algorithm for Generating Discrete Line Transformation of Planar Triangular Grid Based on Weak Duality[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1): 105-110. DOI: 10.13203/j.whugis20180205

基于弱对偶的平面三角形格网离散线转化生成算法

An Algorithm for Generating Discrete Line Transformation of Planar Triangular Grid Based on Weak Duality

  • 摘要: 矢量数据是地球空间数据的重要组成部分,数据离散化是其与栅格数据进行同构处理的重要环节,其中离散线的生成是基本问题。针对三角形格网离散线生成算法的不足,提出了借助弱对偶六边形格网,建立等效三角形格网离散线数学模型,并通过降维方式求解的研究方法。首先,根据三角形格网与六边形格网之间的弱对偶关系,基于六边形格网建立等价的三角形格网离散线模型;然后,利用降维思想将二维离散线模型等价变换为一维闭合路径求解;最后,设计并实现了平面三角形格网离散线转化生成算法。将该算法分别与Freeman算法和全路径算法进行了对比实验,实验结果表明,该算法的运算效率可达同类算法的9~10倍,且效果更优,可应用于矢量数据的实时格网化、地形建模、空间分析、模拟仿真等领域,应用前景广阔。

     

    Abstract: Vector is an important type of geospatial data, discretization is an important link for its fusion with raster data, and the generation of the discrete line is the basic problem. In view of the shortcomings of discrete line generation algorithm of triangular grid, this paper proposes a mathematical model for establishing the equivalent triangle grid discrete line mathematical model by means of the weak duality hexagonal grid and solving it by dimensionality reduction. Firstly, according to the weak duality relationship between the triangular grids and the hexagonal grids, an equivalent triangular grid discrete line model is established based on the hexagonal grids. Then, using the dimension reduction method, the two-dimensional discrete line model is equivalently transformed into a one-dimensional closed path solution. Finally, a discrete triangle conversion generation algorithm for planar triangular grids is designed and implemented. The experimental results show that the proposed algorithm is ingenious and rigorous in theory and beneficial to the programming. The operation efficiency is about 9-10 times of the similar algorithms, with a better result. This algorithm can be applied to vector data in real-time grid transformation, terrain modeling, spatial analysis, simulation and other fields, with broad application prospects.

     

/

返回文章
返回