An improved ray-tracing algorithm based on linear travel-time interpolation

In order to solver for the problem that the original LTI algorithm could not trace the reverse propagation ray, several linear travel-time interpolation (LTI for short) improved algorithms, such as extension-compaction LTI algorithm, loop computation LTI algorithm, the shortest path ray tracing algorithm with dynamic networks, have been presented, but the computational efficiency of these algorithms are low. After analyzing these improved algorithms, this paper presented a new improved shortest path ray tracing algorithm with dynamic networks. According to the law of wave propagation and the basic equation of LTI, a large number of redundancy node calculation are excluded, and the traditional binary heap sort algorithm was used to manage node of wavefront array. The numerical examples show that, the improved algorithm presented in this paper has the highest computational efficiency among all of improved algorithms; its calculation efficiency is about 4.5—30 times of the shortest path ray tracing algorithm with dynamic networks, and about 2—6.5 times of the original LTI algorithm, and about 3.5—15 times of the shortest path ray tracing algorithm with dynamic networks when the traditional binary heap sort algorithm is also used.