# A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
## 2 PLUG Method
### Mapping Relation Between Background Cells and Computational Cells  
As shown in (3), the particle locating on the background grid is straightforward. Thus, the key task in the present study is to find the mapping relation between the background cubes and the computational cells. Please note the term \"cube\" will be used to denote the cells on background grid hereafter to distinguish from computational cells. As mentioned above, the mapping relation should give a integer array [\(a_{II}\), \(a_{I2}\),..., \(a_{Is}\)] for any background cube \(\overline{C}_{I}\), which are the indices of a set of the computational cells [\(C_{aII}\), \(C_{aI2}\),..., \(C_{als}\)] containing or partially overlapping with the corresponding background cube, i.e., satisfying  
\[S_{alq}\cap\overline{S}_{I}\
eq 0(q=0\;\text{to}\;s), \tag{6}\]  
where \(S_{alq}\) is the volume covered by the computational cell \(C_{lq}\) and \(\overline{S}_{I}\) is the volume covered by background cube \(\overline{C}_{I}\). For some background cells, there is a computational cell overlapping with them. Thus, the \(q\) should start from zero in Equation (6). Considering all the background cubes, a list _cube2 cell_ can be obtained, with each component being the above array for the corresponding background cube. The length of the list _cube2 cell_ equals the total number of the background cubes, and parameter s is different for different background cube. In the existing auxiliary grid methods, the size of the background cube is usually larger than that of the computational cell, as shown in Figure 1a. If a cube overlaps with \(n\) (\(n=11\) in Figure 1a) computational cells, the particle-in-cell tests should be conducted for at least \(n-1\) (\(10\) in this case) times to find the its host cell. In PLUG method, the background grid adopts a much smaller grid spacing than that of the computational mesh, as shown in Figure 1b. As a result, the cube-to-cell mapping relation is simplified, i.e. the number of the cells related to a given cube is reduced. An internal cube is completely contained by a computational cell, e.g., cube A contained by cell \(a\). For the particles inside an internal cube, the particle-in-cell test is avoided. A boundary cube, which overlaps with the boundary of the computational cell, is related to only a few nearby cells, e.g., cube \(B\) is only related to cells \(a\) and \(b\). The time-consuming particle-in-cell tests are also reduced. A resulted side effect with the small-spacing background grid is that it is not easy to derive _cube2 cell_ directly. However, an inverse mapping relation can be constructed much more easily, i.e., by finding the background cubes which are fully or partially covered by a certain computational cell. This mapping relation is represented by a list named as _cell2 cube_, with the length being the total number of the computational cell. Each component of this list is still an integer array consisting of the indices of a set of background cubes. For example, considering the computational cell \(C_{J}\), a set of background cubes is \(\left[\overline{C}_{bI},\overline{C}_{bJ2},\widetilde{C}_{bI}\right]\), which are the background cubes fully or partially covered by the corresponding computational cell, i.e., satisfying  
\[S_{bIq}\cap\overline{S}_{J}\
eq 0(q=1\text{ to }t), \tag{7}\]  
where \(\overline{S}_{bIq}\) is the volume covered by background cube \(\overline{C}_{bIq}\) and \(S_{J}\) is the volume covered by computational cell \(C_{J}\). The list _cube2 cell_ is then obtained by applying an inversion operation of the list _cell2 cube_. Using the proposed method for the particle locating, the procedure to specify the mapping relation becomes more complicated compared with the existing methods, where a much larger grid spacing is used on background grid. However, in _cube2 cell_ list, many small background cubes are related to just one computational cell, i.e., \(s=1\), and the point-in-cell test is avoided.