# A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
## 3 Tests and Results  
Three different types of meshes shown in Figure 8 were adopted to test the efficiency of the proposed PLUG method. All these meshes were generated for a cubic domain of \(1\) m \(\times\) 1 m \(\times\) 1 m. In Figure 8, a part of the mesh is cut out to show the mesh cells inside. The hexahedral mesh shown in Figure 8a includes 14,400 cells. The tetrahedral mesh, shown in Figure 8b, generated through Delaunay method, includes 14,333 tetrahedral cells. The polyhedral mesh, shown in Figure 8c, includes 14,645 polyhedral cells. The particles for tests were generated using the following method  
\[\mathrm{x_{p}}=\mathrm{x_{c}}_{l}+0.5V_{j}^{\frac{1}{3}}\left[\mathrm{rand}(-1,1),\mathrm{rand}(-1,1),\mathrm{rand}(-1,1)\right] \tag{9}\]  
where, \(\mathrm{x_{p}}\) is the location of the generated point, \(j\) is the index of a randomly selected cell, \(\mathrm{x_{c}}_{l}\) and \(V_{j}\) are the location of the center and the volume of the cell. Function rand (\(-1\), \(1\)) returns random real number in the range of [\(-1\), \(1\)]. In this study, the binary search method (denoted by octree) and the face-to-face method [6] (denoted by GNH) were adopted, to compare with the proposed PLUG method. The GNH method was conducted with different choices of the starting point, and resulted algorithms are denoted by GNH, GNHNC, and GNHHC. In GNH, the starting point is always located at the center of cell 0. In GNHNC, the starting point for each particle is the center of one of neighbor cells of its host cell. In GNHHC, the starting point is the center of the host cell of each particle. As a result, the operations in GNHNC for each particle are point-in-cell test in starting host cell at first, followed by finding the nearest neighbor cell, which is the correct host cell, and finally the point-in-cell test in the correct host cell. In GNHHC, only the point-in-cell test is conducted, once for each particle, to find the host cell which is exactly the starting host cell. Actually, for a practical computation, the starting point is usually chosen as the center of the host cell at the last time step. GNH, GNHNC, and GNHHC are idealized situations corresponding to worst, near optimal, and optimal choices of the starting point, respectively. Figure 9 shows CPU times consumed by different methods on three different types of meshes, for locating \(1\times 10^{6}\) particles at randomly selected locations in the computational domain. The computational efficiency of the proposed PLUG method depends on the resolution of the background grid on tetrahedral and polyhedral meshes. Figure 9a shows the change of the CPU times with the ratio of the total number of cubes on background grid (\(N_{hc}\)) and the computational cells (\(N_{cc}\)). When \(N_{hc}/N_{cc}<1000\), the computational efficiency was significantly improved by refining background grids. However, it was unworthy of further increasing the resolution of the background grid after that point, because the CPU time decreased little in the cases with the polyhedral mesh and tetrahedral mesh and increased in the case with hexahedral mesh. Moreover, more memory is required to store the  
Figure 8: Three different types of meshes used in numerical tests. (**a**) Hexahedral mesh; (**b**) Tetrahedral mesh; (**c**) Polyhedral mesh. _cube2 cell_ list. On the hexahedral grid, the CPU time was almost independent of the resolution of the background grid because of the same topological structure on the background grid and computational meshes. Comparing the CPU times consumed on the different meshes, particle locating was fastest on the hexahedral meshes, followed by the tetrahedral mesh, which was a little faster than the polyhedral mesh. With the refining background grid resolution, the CPU times finally arrived at the same values with a very fine background grid on different meshes. The CPU times consumed by GNH, GNHNC, GNHHC, and octree methods on different meshes are shown in Figure 9b. GNH method was lowest.