论文研究基于散列函数与半边数据结构的TIN拓扑重构算法.pdf

在以TIN为基础模型的数字化露天矿软件中，TIN拓扑重构是等值线追踪、TIN求交等诸多应用重要的基础算法之一。顶点聚合与边合并是决定TIN拓扑重构效率的关键，应用散列函数根据顶点坐标计算顶点散列地址，并用链地址法辅以AVL树解决地址冲突，以O（N）时间复杂度实现顶点聚合；采用改进的半边数据结构存储TIN，在顶点聚合的同时，通过为每个顶点建立入射半边表，完成半边的快速合并。实验及应用表明，算法时间复杂度近线性，能够满足大数据量条件下TIN拓扑快速重构的需求。