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

发布时间：2021-04-11 09:35

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

【文章来源】：武汉大学学报(信息科学版). 2020,45(01)北大核心EICSCD

【文章页数】：6 页

【部分图文】：

六边形格网与三角形格网对偶关系

作为格网单元计算、定位的参考点[17]，通常以单元中心代替格网单元。因此，为了简化格网转换算法，应尽量使三角形格网与六边形格网单元中心重合。显然，图1所示的对偶关系无法满足该需求。将六边形单元边长调整为，且平行于三角形单元的边，则中心不在三角形顶点处的六边形单元与三角形单元中心重合，如图2所示。本文称该关系为弱对偶，可确保两类格网单元中心最大限度重合，便于格网转换。2 三角形格网离散线模型

在六边形格网中，由某一单元中心指向其相邻单元中心的一组向量称为方向向量。非共线的两个方向向量线性无关，则由起点单元到终点单元的离散线可由任意两个非共线方向向量的有序排列表示。在实际应用中，选择与矢量线ab夹角最小的两个方向向量生成离散线，称为最优方向向量，记作V′={v′0,v′1}，如图3所示。令W′={w′1,w′2?w′N}，w′k为V′中任意元素，离散线单元可表示为u′k=a+w′1+w′2+?+w′k，则以矢量线ab的端点所在单元为起点与终点的离散线为a,u′1,u′2?u′N(b)。仅给定终点与起点，无法唯一确定离散线，因此给出如下限制条件：（1）离散线单元数目最小；（2）在满足（1）的所有离散线中，筛选出的离散线应使最小，d(u′k,ab)为u′k到ab的距离。满足限制条件的离散线是唯一的，且是ab对应的拟合精度最高的离散线，如图4所示。

【参考文献】：
期刊论文
[1]利用球面DQG格网的地形与矢量线自适应叠加算法[J]. 王姣姣,赵学胜,曹文民,董路明.  武汉大学学报(信息科学版). 2014(09)
[2]扫描细化算法的地图自动矢量化研究[J]. 刘人午,李燕.  测绘学报. 2012(02)
[3]地理格网模型研究进展[J]. 周成虎,欧阳,马廷.  地理科学进展. 2009(05)
[4]6步直线生成算法[J]. 贾银亮,张焕春,经亚枝,刘晶.  山东大学学报(工学版). 2007(01)
[5]基于自适应步长的直线生成算法[J]. 黄斌茂,张利.  清华大学学报(自然科学版). 2006(10)
[6]基于线性四叉树的全球离散格网索引[J]. 白建军,赵学胜,陈军.  武汉大学学报(信息科学版). 2005(09)



本文编号：3131016