计算机应用研究2017，Vol.34Issue(12)：3689-3692,3700,5.DOI:10.3969/j.issn.1001-3695.2017.12.038
基于散列函数与半边数据结构的TIN拓扑重构算法
TIN topological reconstruction algorithm based on hash function and half-edge data structure
摘要
Abstract
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.关键词
不规则三角网/拓扑重构/散列函数/半边数据结构Key words
triangulated irregular network(TIN)/topology reconstruction/hash function/half-edge data structure分类
信息技术与安全科学引用本文复制引用
赵景昌,高菲,刘光伟,白润才,王东..基于散列函数与半边数据结构的TIN拓扑重构算法[J].计算机应用研究,2017,34(12):3689-3692,3700,5.基金项目
国家自然科学基金资助项目(51304104,51104084) （51304104,51104084）
中国煤炭工业协会指导性计划项目(MTKJ 2012-306) （MTKJ 2012-306）
辽宁省教育厅科学研究一般项目(L2011051) （L2011051）
