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

TIN topological reconstruction algorithm based on hash function and half-edge data structure

作　　者：赵景昌[1] 高菲[2] 刘光伟[1] 白润才[1] 王东[1] 

机构地区：[1]辽宁工程技术大学矿业学院,辽宁阜新123000 [2]辽宁工程技术大学力学与工程学院,辽宁阜新123000

出　　处：《计算机应用研究》2017年第12期3689-3692,3700,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(51304104;51104084);中国煤炭工业协会指导性计划项目(MTKJ 2012-306);辽宁省教育厅科学研究一般项目(L2011051)

摘　　要：在以TIN为基础模型的数字化露天矿软件中,TIN拓扑重构是等值线追踪、TIN求交等诸多应用重要的基础算法之一。顶点聚合与边合并是决定TIN拓扑重构效率的关键,应用散列函数根据顶点坐标计算顶点散列地址,并用链地址法辅以AVL树解决地址冲突,以O(N)时间复杂度实现顶点聚合;采用改进的半边数据结构存储TIN,在顶点聚合的同时,通过为每个顶点建立入射半边表,完成半边的快速合并。实验及应用表明,算法时间复杂度近线性,能够满足大数据量条件下TIN拓扑快速重构的需求。In the software of digital open pit mine based on TIN model,TIN topology reconstruction is one of the important basic algorithms in the applications of contour tracing,TIN intersection,and so on. Vertex aggregation and edge merging are the keys to determine the efficiency of TIN topology reconstruction. It used hash function to calculate the vertices' hash address,and used the chain address method with the AVL tree to solve the conflict of vertex hash address,vertex aggregation was achieved by O( N) time complexity. It used the improved half-edge data structure to store the TIN,merged the half-edges during the vertices were aggregating by establishing the incident half table for each vertex. Experiments and applications show that the time complexity of the algorithm is nearly linear,it can meet the demand of the TIN topology fast reconstruction under large data quantity condition.

关 键 词：不规则三角网 拓扑重构 散列函数 半边数据结构 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]