基于散列函数与半边数据结构的TIN拓扑重构算法

发布时间：2018-05-01 17:15

  本文选题：不规则三角网 + 拓扑重构　； 参考：《计算机应用研究》2017年12期

【摘要】：在以TIN为基础模型的数字化露天矿软件中,TIN拓扑重构是等值线追踪、TIN求交等诸多应用重要的基础算法之一。顶点聚合与边合并是决定TIN拓扑重构效率的关键,应用散列函数根据顶点坐标计算顶点散列地址,并用链地址法辅以AVL树解决地址冲突,以O(N)时间复杂度实现顶点聚合;采用改进的半边数据结构存储TIN,在顶点聚合的同时,通过为每个顶点建立入射半边表,完成半边的快速合并。实验及应用表明,算法时间复杂度近线性,能够满足大数据量条件下TIN拓扑快速重构的需求。
[Abstract]:In the digital opencast mine software based on TIN, tin topology reconstruction is one of the most important basic algorithms in many applications, such as contour tracing and tin intersection. Vertex aggregation and edge merging is the key to determine the efficiency of TIN topology reconstruction. The hash function is used to calculate the vertex hash address according to the vertex coordinates, and the chain address method is used to solve the address conflict with AVL tree, and the TIN time complexity is used to realize vertex aggregation. The improved half-edge data structure is used to store TIN.While the vertex is aggregated, the incident half-edge table is established for each vertex, and the fast merging of half-edge is completed. Experiments and applications show that the time complexity of the algorithm is nearly linear and can meet the need of fast TIN topology reconstruction under the condition of large amount of data.
【作者单位】： 辽宁工程技术大学矿业学院;辽宁工程技术大学力学与工程学院;
【基金】：国家自然科学基金资助项目(51304104,51104084) 中国煤炭工业协会指导性计划项目(MTKJ 2012-306) 辽宁省教育厅科学研究一般项目(L2011051)
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 王建群;高职数据结构课教学方法初探[J];辽宁教育行政学院学报;2004年05期

2 李延明;数据结构在程序设计中的实用分析[J];江汉石油职工大学学报;2004年04期

3 黄伟焕;;高职“数据结构”教材编写中应把握的几个原则[J];温州职业技术学院学报;2005年04期

4 邓安远;万红艳;;“数据结构”课程教学的研究与探讨[J];计算机教育;2007年08期

5 范德宝;于晓聪;丁伟祥;;提高数据结构课程教学效果的探讨[J];黑龙江科技信息;2007年17期

6 葛亚平;李春生;王巧玲;;数据结构在游戏中的应用[J];今日科苑;2007年12期

7 汪沁;奚李峰;杨秀金;;基于“数据结构”实验的探讨和研究[J];中国教育信息化;2007年07期

8 武刚;;“数据结构”课程的教学探讨[J];科技信息(学术研究);2007年30期

9 杨永斌;;“数据结构”教学策略探讨[J];合肥工业大学学报(社会科学版);2008年03期

10 张一倩;;谈高职数据结构的教学方式[J];科技信息(科学教研);2008年24期

相关会议论文 前10条

1 赵亚男;王晓明;郭进;;微机联锁系统健壮数据结构的研究[A];2004全国测控、计量与仪器仪表学术年会论文集（下册）[C];2004年

2 刘亚波;刘大有;高滢;;以实验教学深化“数据结构”理论教学[A];2005全国计算机程序设计类课程教学研讨会论文集[C];2005年

3 胡学钢;张晶;周红鹃;张玉红;王德兴;;数据结构实践教学体系设计[A];2005全国计算机程序设计类课程教学研讨会论文集[C];2005年

4 王金凤;谢扬;;论“数据结构”教学改革[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

5 吕春莲;;统计数据库逻辑设计与数据结构研究[A];第十二届全国数据库学术会议论文集[C];1994年

6 玄钟伍;王炳宇;张德琪;;多层数据模型图形数据库数据结构[A];第九届全国数据库学术会议论文集(下)[C];1990年

7 程乾生;;非线性时间序列预测——基于数据结构的预测方法[A];全国第一届嵌入式技术联合学术会议论文集[C];2006年

8 楼荣生;施伯乐;;自调整的有序散列函数[A];第十届全国数据库学术会议论文集[C];1992年

9 盛素英;;逻辑数据结构LDS[A];第十届全国数据库学术会议论文集[C];1992年

10 赵国玲;;课程综合——中等专业学校课程改革的重要途径[A];2001中国电子教育研究论文集[C];2001年

相关重要报纸文章 前2条

1 重庆 Over-Time;程序=算法+数据结构[N];电脑报;2004年

2 黄凌云;巧妙安排计费工程中的对账工作[N];通信产业报;2004年

相关博士学位论文 前1条

1 何加亮;基于散列函数的RFID安全协议研究[D];吉林大学;2012年

相关硕士学位论文 前10条

1 于治越;程序代码资源解题算法与其数据结构关联研究[D];东华大学;2013年

2 董文华;基于安卓的数据结构学习系统设计与实现[D];内蒙古大学;2016年

3 刘文韬;Blender 3D渲染机制研究[D];南京邮电大学;2016年

4 金雷过;BOM数据结构及其应用研究[D];东南大学;2016年

5 孟凡力;百度文库用于改善学生数据结构成绩预测的研究[D];重庆大学;2016年

6 陆易凡;基于GPU的树形结构数据处理[D];东南大学;2016年

7 赵兰草;QAR数据的异常检测与分析算法研究[D];中国民航大学;2014年

8 谢明师;3D打印预处理软件设计与实现[D];中北大学;2017年

9 李桢;数据结构及算法动态演示平台设计与实现[D];大连海事大学;2017年

10 李鹏;外存储算法中两个数据结构的设计研究[D];兰州理工大学;2011年

，

本文编号：1830320