# Multi-UAV Area Coverage Track Planning Based on the Voronoi Graph and Attention Mechanism
## 3 Method  
### Region Division Algorithm  
By subdividing a complex or extensive area into smaller, more manageable units, a region partitioning algorithm optimizes resource allocation and management while enhancing the efficiency and accuracy of data processing, analysis, and decision-making. This algorithm computes the Voronoi diagram of a planar polygon defined by \(n\) straight lines. The steps of the algorithm are as follows. Firstly, the linear function representing the side lengths of a planar polygon is shown in Equation (1). \[f_{1}(x,y)=0,f_{2}(x,y)=0,\cdots,f_{n}(x,y)=0 \tag{1}\]  
where the domain \([x,\overline{x}]\times[y,\overline{y}]\) is a rectangular region in the plane and the pixel size (i.e., the length or width of the pixel). Next, compute the Voronoi diagram of the polygon formed by these n-line segments within this rectangular region. Specifically, identify the n sets of pixels \(A_{1}=\bigcup_{i=1}^{k_{1}}\{[a_{1i},b_{1i}]\times[c_{1i},d_{1i}]\},\cdots,A_{n }=\bigcup_{i=1}^{k_{n}}\{[a_{ni},b_{ni}]\times[c_{ni},d_{ni}]\}\) encompassing these n-line segments in the entire pixelated area. Secondly, utilize modified affine arithmetic \(f_{1}(x,y)\) to determine the range of \([x,\overline{x}]\times[y,\overline{y}]\) within the rectangular region \(\left[f,\overline{f}\right]\). If the range \(\left[f,\overline{f}\right]\) of does not include zero, it implies that the region \([x,\overline{x}]\times[y,\overline{y}]\) does not intersect the line segment \(f_{1}(x,y)=0\), and thus, this region can be discarded. Otherwise, bisect the region \([x,\overline{x}]\times[y,\overline{y}]\) into four subregions at its midpoint and reiterate Step 2 for each subregion until both the length and width of the region are less than or equal to the pixel size. If the region remains non-excludable, store this region in \(A_{1}\). This process yields \(A_{2},\cdots,A_{n}\). Thirdly, the subsequent critical step involves computing the set of pixels M within the rectangular region \([x,\overline{x}]\times[y,\overline{y}]\) where the distance to the n sets of pixel collections \(A_{1},\ A_{2},\cdots,\text{and}\ A_{n}\) is minimized at least at two points. We use interval arithmetic and the quadtree algorithm to address this problem. Initially, standard interval arithmetic was to calculate the interval distance \([g_{i},\overline{g_{i}}]=\sqrt{\left([x,\overline{x}]-[a_{1i},b_{1i}]\right)^{2 }+\left([y,\overline{y}]-[c_{1i},d_{1i}]\right)^{2}}\) between the rectangular region \([x,\overline{x}]\times[y,\overline{y}]\) and each pixel \([a_{1i},b_{1i}]\times[c_{1i},d_{1i}]\) individually. Then let \(l_{i}=\underset{1<l<K_{1}}{min}\{g_{i}\}\), \(h_{i}=\underset{1<l<K_{1}}{min}\{\overline{g_{i}}\}\) the interval obtained \([l_{1},\ h_{1}]\) represents the shortest distance interval from the rectangular region \([x,\overline{x}]\times[y,\overline{y}]\) to the line segment. Similarly, compute the shortest distance interval from the rectangular region \([x,\overline{x}]\times[y,\overline{y}]\) to the line segment \(\text{A}_{n}\), resulting in the interval \([l_{n},\ h_{n}]\). Let \(l=\underset{1<i<n}{min}\{l_{i}\}\), \(h=\underset{1<i<n}{min}\{l_{i}\}\), then \([l,h]\) is defined as the interval of the shortest distance from the rectangular region to the n plane line segments. If only a single interval between \([l,h]\) and \(\{l_{i},\ h_{i}\},1<i<n\) intersects, we can discard it. However, if at least two intervals intersect with \([l,h]\) and \(\{l_{i},\ h_{i}\},1<i<n\), then the area \([x,\overline{x}]\times[y,\overline{y}]\) is divided into four parts at the midpoint. Through the recursive process of the quadtree, the subdivided parts of the area are gradually reduced until the subdivided area length and width are both less than or equal to \(\varepsilon\) If the region remains non-excludable, store this region in M. Finally, the set M represents the Voronoi diagram of the polygon. Render the planar line segments \(A_{1},\ A_{2},\cdots,A_{n}\) and the Voronoi diagram M. The algorithm is complete.