# A Fast Particle-Locating Method for the Arbitrary Polyhedral Mesh
## 2 PLUG Method
### Particle Locating  
PLUG uses different procedures to find the host cell for a given particle within different types of host background cubes. In PLUG, background cubes are categorized into three different types (as shown in Figure 7). Figure 6: An illustration of a _cube2 cell_ list. * **Exterior cubes. ** There are some background cubes which are not covered by any computational cell, since the physical domain covered by background grid is a little larger than the computational domain, as we have mentioned in Section 2.1. In this case, the corresponding component in the _cube2 cell_ list is empty. * **Boundary cubes. ** The boundary elements are the cubes near the boundary surface of the computational domain. One can find the background cubes for a given polygonal face on boundary with the same method as that for finding those for a given computational cell. A general polygon is decomposed into several triangles. The characteristic points for searching are shown in Figure 4b, and the subdivision process for a triangle is the same as that for the boundary surface of a tetrahedron, as shown in Figure 5b. * **Interior cubes. ** All the elements, excluding exterior cubes and boundary cubes belong to this type. Similar to the _cube2 cell_ list, the element types are decided just once before the simulation with a fixed computational mesh. In order to find the host cell for a given particle, the host cells on background grid are determined using (3). If the indices satisfy \(i\in[0,n_{x}-1]\), \(j\in\left[0,n_{y}-1\right]\) and \(k\in[0,n_{z}-1]\), the point is inside the domain of the background grid. Otherwise, the point is outside the background grid, and it will not be inside any cell of the computational mesh. For the point inside the background grid, three situations are considered, corresponding to the type of the host background cell as  
* For particles inside an exterior cube, these particles are outside the computational domain and not in any polyhedral computational cell. * For particles inside a boundary cube, the point-in-cell test is adopted to check whether these points are inside one of the computational cells stored in the corresponding component of the _cube2 cell_ list. If a computational cell is found, it is the host cell. Otherwise, this particle is out of the computational domain. * For particles inside an interior cube, the point-in-cell test is carried out to find the host cell. It is worth nothing that, in this case, some background cubes are contained by only one computational cell, and only one index appears in the corresponding component of the _cube2 cell_ list. In this case, the host cell can be determined without any point-in-cell test. This makes the PLUG method much more efficient than existing point locating algorithms. Figure 7: Different types of the background cubes. For those problems where particles are always inside the solution domain, there is no need to distinguish the types of the background cubes. However, for an open system, though there is only one index stored in some components of the _cube2 cell_ list, the corresponding computational cell may not be the host cell. If the background cube is a boundary cube, the particle may be out of the computational domain. So far, the remaining task is to check whether a point is inside a polyhedral cell or not, i.e., the point-in-cell test. We first carry out a plane testing for each boundary surface of the computational cell as  
\[l=\mathbf{n}\cdot\left(x_{p}-x_{c}\right) \tag{8}\]  
where \(\mathbf{n}\) is the outward normal direction of a boundary surface, \(\mathrm{x_{p}}\) is the location of the tested point, and \(\mathrm{x_{c}}\) is the location of centroid of the surface. Equation (8) is tested for all boundary surfaces of a computational cell. If \(l>0\) for some surface, the point will be outside the cell, otherwise, it is inside the cell. If the boundary surface is triangle, the above test can be applied directly.