## 3 Air-Ground NLOS Identification Method Aided by 3D Terrain Modelling
### Air-Ground Member-Ray Terrain Intersection Detection Methods
The octree data structure and the process of dividing the child nodes are shown schematically in Figure 4.  
First, to initialize the octree, in this paper, the maximum depth was set to 16, and there are at most \(2^{16}\times 2^{16}\times 2^{16}\) voxel structures. The coordinates \(\mathbf{v}_{i}^{G}=\left(v_{i}^{x},v_{i}^{y},v_{i}^{z}\right)^{T}\) of the voxels in the octree can be queried based on the point cloud 3D coordinates \(\mathbf{p}_{i}^{G}=\left(x_{i},y_{i},z_{i}\right)^{T}\)[20]. Within the topography of the octree, the voxel \(V_{i}\) generally has three states: occupied, free and unknown. By dividing the octree voxels into occupied and free cases, the requirements for an NLOS identification method for air-ground swarm cooperative navigation can be met. This paper is not concerned with the application of an unknown state to the octree. Figure 4: Diagram of the octree structure. Figure 3: LOS signal ruled out by mistake. The definition of light rays is given by the following equation [28]:  
\[\vv{x}=\vv{p}+t\vv{d} \tag{1}\]  
where \(\vv{p}=\left(p_{x},p_{y},p_{z}\right)\) is the starting point of the ray, \(\vv{d}=\left(d_{x},d_{y},d_{z}\right)\) is the unit vector representing the direction of the ray, \(t\) is the length of the ray, and \(\vv{x}\) is the end point of the ray. As an example, the ray detection algorithm for all \(\vv{d}>0\) cases are described in the following section for two-dimensional quadtree intersection detection. The algorithm is also applicable to all other cases. The intersection of ray/octree maps shown n Figure 5.  
If \(\vv{d}>0\), to determine the order of the child nodes that should be traversed, it is necessary to determine which child node the ray hits first. \(t_{xii},t_{yi}(i=0,1)\) is the distance from the starting point of the ray to the intersection of the horizontal and vertical axes of the node boundary, \(t_{xm},t_{ym}\) is the length of the ray, the first comparison between \(t_{xm}\) and \(t_{ym}\) determines whether the ray intersects with q1 or q2 of the child node, and the second comparison between \(t_{xii},t_{yi},t_{xm},t_{ym}\) determines whether the ray intersects with q0 or q3, thus obtaining a judgment of which child node of the node the ray intersected with first; the process of the judgment is shown in Figures 6 and 7:  
Figure 5: Intersection of ray/octree maps. Figure 6: Intersection judgment in the case \(t_{y}^{m}<t_{x}^{m}\). Figure 7: Intersection judgment in the case \(t_{y}^{m}>t_{x}^{m}\). In 3D terrain modelling octree ray intersection detection, a single node contains eight child nodes, for which the \(t_{z0}\), \(t_{z1}\) and \(t_{zm}\) parameters on the \(z\)-axis need to be calculated. Therefore, intersection detection requires more judgment but the detection principle is like that of 2D intersection detection [29]. Through the above method, if the ray intersects the 3D octree map, the intersection points of the light ray and the 3D octree map as well as the length of the light ray can be obtained, which lays the foundation for the cooperative navigation NLOS error suppression method based on air-ground visibility analysis in this article.