计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (24): 10-15.

• 博士论坛 • 上一篇    下一篇

一种基于TIN的等值线快速生成算法

赵景昌1,白润才1,刘光伟1,刘  威2   

  1. 1.辽宁工程技术大学 矿业学院,辽宁 阜新 123000
    2.辽宁工程技术大学 理学院,辽宁 阜新 123000
  • 出版日期:2014-12-15 发布日期:2014-12-12

Fast isolines generation algorithm based on TIN

ZHAO Jingchang1, BAI Runcai1, LIU Guangwei1, LIU Wei2   

  1. 1.School of Mining, Liaoning Technical University, Fuxin, Liaoning 123000, China
    2.College of Science, Liaoning Technical University, Fuxin, Liaoning 123000, China
  • Online:2014-12-15 Published:2014-12-12

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

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

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