A Fast Algorithm of the Shortest Path Ray Tracing
Meigen Zhang, Bingjie Cheng, Xiaofan Li, Miao-Yue WANG · Chinese Journal of Geophysics · 2006
Abstract To raise the accuracy of the shortest path ray tracing, it is usually necessary to represent the model with dense grids and nodes, and to increase ray directions emanating from a secondary source, or to improve the results with other algorithms. All these measures bring forth many additional computations. The fast algorithm presented in this paper greatly enhances the efficiency of the traditional shortest path ray tracing with more efficient management of wavefront nodes and more efficient computation of the secondary wave propagation. The bucket sort is applied to manage wavefront nodes, which is superior to the heap sort used in the tradition method. In addition, both Snell's law and the traveltime information of waves from neighboring nodes are considered to determine the effective propagation area of a secondary source. Thus, many unnecessary propagation directions are excluded. Numerical tests show that the speed of the fast algorithm is about several to more than ten times of that of the traditional method.