Abstract: Generating isogram based on TIN is one of the important means to recover the geological properties and variables distribution with the finite discrete spatial information. Its time efficiency mainly depends on the initial edge with isoline point checking and isolines tracking. By building the red-black tree with triangular facets units as TIN node, the time complexity of the initial edge checking is improved from [O(M×N)] to [O(lbN)]; TIN topology is reconstructed based on hash and half-edge data structure. According to “side-face” topology, isolines tracking is synchronously completed with the isoline points interpolation. Experiments and practical application show that the algorithm is stable, the precision of the isolines generation is reliable, and the algorithm can meet the needs to quickly generate isolines with the large amount of data, and has a wide range of practical application value.

Key words: Triangulated Irregular Network（TIN）, isoline, red-black tree, hash, half-edge data structure, topology reconstruction

摘要： 基于TIN生成等值线图是利用有限的离散空间信息恢复地质属性和地学变量空间分布状态的重要手段之一，其时间效率主要取决于起始等值边查找与等值线追踪。通过构建以TIN三角面片单元为节点的红黑树，将起始等值边查找的时间复杂度由[O(M×N)]提高到[O(lbN)]；基于散列与半边数据结构重建TIN拓扑，根据TIN中“边—面”拓扑关系，在等值点内插计算的同时完成等值线追踪。实验及应用表明，算法时间效率高，生成的等值线精度可靠，可满足大数据量条件下等值线快速生成的需要，具有广泛的实际应用价值。

关键词: 不规则三角网（TIN）, 等值线, 红黑树, 散列, 半边数据结构, 拓扑重构