# An Efficient GNSS Coordinate Recognition Algorithm for Epidemic Management
## 4 Coordinate Recognition Algorithm
### The Proposed Algorithm
This algorithm is used to evaluate a minimal rectangular space that completely covers polygon \(P\). Applying it will result in four values, i.e., \(x_{min}\), \(x_{max}\), \(y_{min}\), and \(y_{max}\). The dataset \(R\) contains these  
```
1.\(count\_pt:=0\);
2.for\(i:=0\) to \(3\)do
3.if(PUnPy(\(s_{i}\), \(P\) = 1)
4.then\(count\_pt:=count\_pt+1\);
5.endif
6.endfor
7.\(count\_edge:=0\);
8.for\(j:=0\) to \(n-1\)do
9.for\(i:=0\) to \(3\)do
10.\(g_{a}:=p_{j}\);
11.\(g_{b}:=p_{j+1}\);
12.\(g_{c}:=s_{i}\);
13.\(g_{d}:=s_{i+1}\);
14.if(SegSegInt(\(g_{a},g_{b},g_{c},g_{d}\)) = 1)
15.then\(count\_edge:=count\_edge+1\);
16.endif
17.endfor
18.endfor
19.if(\(count\_pt\) = 4 and \(count\_edge=0\)) then\(status:=0\);
20.elseif(\(count\_pt\) = 0 and \(count\_edge=0\)) then\(status:=2\);
21.else\(status:=1\);
22.endif
23.return\(status\);
```  
**Algorithm 3**SqrInPy(square \(S\), polygon \(P\))  
```
1.\(x_{min}:=p_{0,x}\); \(x_{max}:=p_{0,x}\); \(y_{min}:=p_{0,y}\); \(y_{max}:=p_{0,y}\);
2.for\(j:=1\) to \(n\)do
3.if\(p_{j,x}<x_{min}\)then\(x_{min}:=p_{j,x}\); endif
4.if\(p_{j,x}>x_{max}\)then\(x_{max}:=p_{j,x}\); endif
5.if\(p_{j,y}<y_{min}\)then\(y_{min}:=p_{j,y}\); endif
6.if\(p_{j,y}>y_{max}\)then\(y_{max}:=p_{j,y}\); endif
7.endfor
8.\(R:=\{x_{min},x_{min},y_{min},y_{max}\}\);
9. return (\(R\));
```  
**Algorithm 4**RectOfPy(polygon \(P\))  
The application of Algorithm 4 results in a dataset \(R\). The values of dataset \(R\) define the range of a polygon. The dataset \(R\) contains four values, and \(R[0]\), \(R[1]\), \(R[2]\), and \(R[3]\) represent these values. Algorithm 5 is used to divide this polygon into several squares of equal size, where the side length of each square is \(sl\). Algorithm 5 is the RectPtnToSqr algorithm. It is a rectangle-partition-to-square algorithm, and its inputs are the five values of \(x_{min}\), \(x_{max}\), \(y_{min}\), \(y_{max}\), and \(sl\). It uses the values of \(x_{min}\), \(x_{max}\), \(y_{min}\), and \(y_{max}\) to define the range of a rectangle into its length and width, respectively (\((x_{max}-x_{min})\) and \((y_{max}-y_{min})\)). It then partitions the range into a set \(SS\) of \(numx\times numy\) squares, where ceiling() is applied. The ceiling() function is a least-integer function. Its input is a real number, and its output is an integer that is not smaller than the input value. This set defines each square \(S\) by using its upper-left vertex (\(s_{0.x}\), \(s_{0.y}\)). Accordingly, square \(S\) can be defined by using \(s_{0}\) and the side length sl. Algorithm 6 is the CoordRecognit algorithm. It is a coordinate recognition algorithm, and its inputs are a polygon \(P\), a point set \(G\), and the side length \(r\) of a square. Applying it will return all inner points of polygon \(P\). This algorithm first defines a rectangle \(R\), which can cover polygon \(P\), through RectOffy. Next, this rectangle \(R\) is partitioned into \(SS\), a set of squares \(SS\) with a side length \(sl\), through RectPntToSquare. For each square \(s_{0}\) of \(SS\), where \(s_{0}\) is the upper-left vertex of the square, its vertices are composed of a square \(S=\{s_{0},s_{1},s_{2},\)\(s_{3},s_{4}(=s_{0})\}\). Then, the space-overlap status between square \(S\) and polygon \(P\) is evaluated through SqrInPy. If \(S\) is an inner square of or a square intersecting with polygon \(P\), i.e., \(status=0\)**or**\(status=1\), the SQL statement is queried in order to retrieve the inner points from table 'Q', and they are stored in set \(G_{T}\). If \(S\) is an inner square of \(P\), i.e., \(status=0\), set \(G_{T}\) is directly stored in set \(G_{P}\). If \(S\) is a square intersecting with \(P\), i.e., \(status=1\), each point \(g\) of \(G_{P}\) must be confirmed through PntInPy. If point \(g\) is an inner point of \(P\), incrementally, point \(g\) is stored in \(G_{P}\). Finally, \(G_{P}\) is the set of all inner points of \(P\).