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

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

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

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

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.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

摘要/Abstract

摘要： 基于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

赵景昌1，白润才1，刘光伟1，刘威2. 一种基于TIN的等值线快速生成算法[J]. 计算机工程与应用, 2014, 50(24): 10-15.

ZHAO Jingchang1, BAI Runcai1, LIU Guangwei1, LIU Wei2. Fast isolines generation algorithm based on TIN[J]. Computer Engineering and Applications, 2014, 50(24): 10-15.

[1]	杜宏伟，乔美丽，宋刚，张云峰，包芳勋. 基于视觉感知的图像放大[J]. 计算机工程与应用, 2020, 56(9): 204-212.
[2]	张敏，杜伟章. 自选子秘密可公开验证可更新多秘密共享方案[J]. 计算机工程与应用, 2016, 52(9): 71-77.
[3]	张敏，杜伟章. 可公开验证可定期更新的多秘密共享方案[J]. 计算机工程与应用, 2016, 52(2): 117-126.
[4]	王灿1，乔建华1，2，闫庆森1. 一种基于散列链的自适应网格安全路由协议[J]. 计算机工程与应用, 2015, 51(2): 108-112.
[5]	林俊锋，黄常标，祁杨停. 三角网格模型分治加工中区域分割算法的研究[J]. 计算机工程与应用, 2015, 51(12): 184-188.
[6]	黄秋兰，程耀东，陈刚. 分布式存储系统的哈希算法研究[J]. 计算机工程与应用, 2014, 50(1): 1-4.
[7]	李强1，李超2，甘建红3. 基于三角网的等值线填充算法研究[J]. 计算机工程与应用, 2013, 49(5): 185-189.
[8]	何滨，杜伟章. 前向安全无证书代理盲签名方案的分析与改进[J]. 计算机工程与应用, 2013, 49(22): 104-109.
[9]	宋敦江1，毕诚2，岳天祥3. 由等高线重构曲面的HASMOC方法应用研究[J]. 计算机工程与应用, 2013, 49(18): 171-175.
[10]	李志灿1，王奕1，2，3，李仁发1，2，3. 可重构Gr?stl设计研究及其FPGA实现[J]. 计算机工程与应用, 2012, 48(6): 49-52.
[11]	赵红波1，张涵2. 一种等值线图的任意复杂多边形窗口裁剪算法[J]. 计算机工程与应用, 2012, 48(32): 170-175.
[12]	张宇，文中领，张延枫. 一种在存储子系统中实现依赖快照的技术[J]. 计算机工程与应用, 2011, 47(5): 53-56.
[13]	赵欢欢，许勇，朱晓伟. 安全多播密钥更新机制优化方案[J]. 计算机工程与应用, 2011, 47(34): 98-100.
[14]	陈学工，付金华，马金金，邱华. 约束TIN生成带断层等值线图的方法[J]. 计算机工程与应用, 2011, 47(33): 198-201.
[15]	徐华¹，武强²，张晓亮²，何畏². 基于拓扑重构的流线特征跟踪算法[J]. 计算机工程与应用, 2010, 46(9): 234-237.