一种最短路径射线追踪的快速算法

为提高最短路径射线追踪的精度，需要增加模型的剖分网格和离散节点，并增加子波传播方向，或者采用其他方法改善计算结果，这些处理会带来大量的额外计算.本文的快速算法改进了波前点的管理和子波传播的计算这两项耗时的工作，较大幅度地提高了传统算法的效率.在波前点的管理上，采用按时间步划分区间的方法，实现了波前点的桶排序管理，其效率高于传统方法中常用的堆排序算法. 在子波传播的计算上，利用斯奈尔定律，同时参考来自邻近节点的波的走时，来限定当前子波传播的有效区域，排除大量不需要计算的子波传播方向. 模型实算表明，本文快速算法的计算速度是传统方法的几倍至十多倍.

A fast algorithm of shortest path ray tracing

To get accurate results with 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.These measures bring forth many additional computations.This paper presents a fast algorithm with more efficient management of wavefront nodes and more efficient computation of the propagation of a secondary source than the traditional method.In this method,the bucket sort is applied to manage wavefront nodes.It is more efficient than the heap sort used in the traditional method.In addition,Snell's law is applied,and traveltimes of waves from neighboring nodes are considered at the same time to determine the effective propagation area of the current 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.