# Clustering Method of Large-Scale Battlefield Airspace Based on Multi A * in Airspace Grid System
## 4 Airspace Clustering Steps Based on Multi-A \({}^{*}\) Algorithm  
### Construct Airspace Security Bounding Box  
The method of building bounding boxes for polygons is mainly an effective method to solve the problem of polygon intersection in the horizontal dimension. A bounding box with a slightly larger area and relatively simple geometric features is used to approximately describe more complex polygons. Because the intersection test of bounding boxes is relatively simple, the time consumption is very small compared with the accurate conflict detection between polygons. The application in the field of battlefield airspace management and control mainly has two functions: first, by setting the size and width of the bounding box, the airspace can reach the specified airspace safety separation distance. Second, it is convenient to judge the conflict of task airspace and improve the efficiency of battlefield airspace management and control. For bounding boxes, the following two constraints are generally required:1. Simplicity: The bounding box itself should be a simple geometric figure relative to the surrounded polygons. In addition, the intersection test of the bounding box should be relatively simple, otherwise it will affect the efficiency. 2. Tightness: The bounding box should be as close to the polygon as possible, and closely enclose the polygon. Common bounding boxes mainly include spherical bounding box (SBB) [68], aligned axis bounding boxes (AABB) [69; 70], and oriented bounding boxes (OBB) [71; 72; 73], as shown in Figure 1.  
The construction method of spherical bounding box and AABB is simple, but the disadvantage is that the compactness is not strong. If there is a large amount of airspace in a region, both the bounding balls and AABB in the airspace are easy to overlap, resulting in no significant reduction in the number of airspace pairs that require refined polygon intersection testing. The OBB bounding box is more flexible in direction selection than the bounding sphere and AABB due to its compact enclosure. It is widely used by researchers and can relatively accurately eliminate the airspace pairs that do not overlap on the horizontal plane. In this paper, the airspace is abstracted as regular polygons, so the overall effect of axial bounding box and directional bounding box is similar, this article mainly introduces the construction method of the direction bounding box. The smallest rectangle containing the polygon and arbitrary relative to the coordinate axis direction. Its direction is not fixed, so we can find an optimal surrounding polygon with relatively tight direction through calculation. The direction of the OBB should be able to contain most of the polygon information. This section uses Principal Component Analysis (PCA) to construct the OBB. OBB generation steps based on principal component analysis (PCA) are as follows:  
Suppose the polygon has \(m\) vertices in total, and the coordinates of the \(i\) vertex are expressed as \((x_{i},y_{i})\), where \(1\leq i\leq m\). Step 1: Construct vertex coordinate matrix: \(m\) vertex coordinates are formed into matrix \(A_{m\times 2}\), and each matrix \(A\) represents the coordinates of a vertex;  
Step 2: Zeroing mean value: calculate the mean value of each column vector of matrix \(A\), and subtract the mean value of this column vector from each column vector element to obtain the zeroing mean value matrix \(X\);  
Step 3: Find the covariance matrix \(C\) of the zeroing average matrix \(X\), where \(C=\frac{1}{m}X^{T}X\). Step 4: Find the eigenvector of the covariance matrix. The directions of the two eigenvectors \(n_{1}\) and \(n_{2}\) are the two axes of the OBB bounding box, and the eigenvector matrix \(N_{2\times 2}\), \(N=[n_{1},n_{2}]\) is constructed. Step 5: Coordinate rotation transformation. The projection coordinates of polygon vertex coordinates on two axes of OBB bounding box are obtained to form matrix \(B\), \(B_{m\times 2}=A_{m\times 2}\times N_{2\times 2}\).