# A Fast Ray-tracing Method for Locating Mining-induced Seismicity by Considering Underground Voids
## 2 Methodology
### A Fast Ray-tracing Method
#### Implementation  
After modeling, we perform ray tracing. First, to improve the accuracy of ray tracing, we arrange nodes on the edge according to the step length s. The nodes are divided into two categories. The first category of nodes is the vertex of the void, and the second category of nodes is arranged on the edge. The step size s controls the accuracy of ray tracing. The smaller the s, the more the number of the second category of nodes. Generally, we set the step size s according to the actual situation. 1. [leftmargin=*]
2. Arrange the second category nodes  
We first make the following statement: \(Nc\), \(Np\) represent the number of vertices, and the number of triangular faces of the model, respectively. \(v\) represents the propagation velocity of the wave in the non-voids. The number of edges in the model is 3\(Np\)/2. The number of nodes we arrange on the \(i\)-th edge is:  
\[LN_{i}=[D_{i}/s] \tag{1}\]  
where \(LN_{i}\) represents the number of nodes arranged on the \(i\)-th edge. Di is the length of the \(i\)-th edge and \([X]\) represents the largest integer not greater than \(X\). Then the total number of nodes arranged on the edges is:  
\[Na=\sum_{i=1}^{n}LN_{i},n\leq 3 Np/2 \tag{2}\]  
where \(Na\) is the total number of the second category nodes. The number of nodes of the first category plus that of the second category is the total number of nodes. \[Ns=Nc+Na \tag{3}\]  
where \(Ns\) is the total number of nodes. Let us take the model in Figure 3 as an example. There are 4 nodes of the first category (black circle) and 13 nodes of the second category (red circle). If we want to improve the accuracy of ray tracing, we only need to reduce s. The number of nodes of the second category increases, but the number of nodes of the first category remains unchanged. Figure 2: A simple void model. 2. Adjacent nodes of each node  
In addition to the two categories of nodes on the above model, we must have a source and a receiver. Therefore, we get a collection of all data, denoted as _Datas_. \[\textit{Datas}=\{N,S,R\} \tag{4}\]  
where \(N\) is the collection of nodes on the model. \(S\) and \(R\) are the source and receiver, respectively. The definition of adjacent nodes is as follows: If the straight line from node A to node B does not pass through the voids, then A and B are adjacent nodes to each other; otherwise, they are not adjacent nodes. The method of judging adjacent nodes is as follows: We turn this question into a question of whether a certain point is in a void. See reference [23] for the algorithm to determine whether the point is in the void. As shown in Figure 4, we first judge whether the midpoint C of node A and node B is in the void. If C is in the void, A and B are not adjacent nodes; otherwise, continue to judge whether D and E are in the void until the allowable tolerance c is reached. Please see Figure 5 for the detailed process. Figure 4: Schematic diagram of dividing the line AB into n equal parts. C and D, E are the points where the line segment AB is halved and quartered, respectively. Figure 3: Two categories of nodes on the model. The black circle and the red circle represent the first category node and the second category node, respectively. 3. Ray tracing  
Finally, we perform the shortest path from the source to the receiver based on the Dijkstra algorithm. We divide the _Datas_ obtained from Equation (4) into three sets. \(P\) represents the set of nodes that have not got the arrival time. \(Q\) represents the set of nodes that have got the arrival time but have not been the source. \(K\) represents the set of nodes that have been the source. **Step 1:** Initialization  
\[P=\{N,R\},Q=\varnothing,K=S \tag{5}\]  
**Step 2:** Calculate the arrival time from the source \(S\) to each of its adjacent nodes according to Equation (6). \[t_{i}=\sqrt{\left(x_{s}-x_{i}\right)^{2}+\left(y_{s}-y_{i}\right)^{2}+\left(z _{s}-z_{i}\right)^{2}}/v+t_{s},i\in J(s) \tag{6}\]  
where \(t_{s}\) and \(t_{i}\) are the arrival time of \(S\) and the \(i\)-th node, respectively.