# An Efficient GNSS Coordinate Recognition Algorithm for Epidemic Management
## 4 Coordinate Recognition Algorithm
### The Proposed Algorithm
\begin{table}
\begin{tabular}{c c} \hline \hline
**Function** & **Description** \\ \hline SegSegInt & The input required by this function is two line segments, which can be used to calculate whether the two line segments intersect. \\ \hline PtInPy & The input required by this function is a geographical point and a polygon. First, the function uses SegSegInt to calculate the intersections among the ray of this point and the edges of this polygon. Then, it calculates whether the geographical point is inside the polygon based on the result. \\ \hline SqrInPy & The input required by this function is a square and a polygon. In this function, PtInPy is used to calculate whether the four points of the square are inside the polygon. According to this result, the spatial relationship between the square and the polygon is divided into inner, outer, and intersected. \\ \hline RectOfPy & The input required by this function is a polygon, and it will identify a minimum rectangle that can cover this polygon. \\ \hline RectPtnToSqr & The input required by this function is a coordinate range that can identify a rectangle, and it will divide the range of this rectangle into a square set. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Functions. Applying it will result in a value of 1 or 0, which will indicate if \(g\) is an inner point of \(P\) or if \(g\) is an outer point of \(P\). In this algorithm, the _count_ variable is used to count the number of intersections between the rays of \(g\) and the \(n\) edges of \(P\). Here, mod(_count_, 2), which is a modulo operation that returns the remainder after _count_ is divided by 2, is used. It combines each edge (\(p_{i}\), \(p_{i+1}\)) of \(P\), where \(i=0\), \(1\),..., \(n-1\), and point \(g\) into the segment (\(g_{a}\), \(g_{b}\)) and the segment (\(g_{c}\), \(g_{d}\)). If the two segments intersect, the value of _count_ is increased by 1. Finally, if the value of _count_ is even (i.e., mod(_count_, 2) = 1), it returns 0. Otherwise, it returns 1. ```
1.\(count:=0\);
2.for\(i:=0\) to \(n-1\)do
3.\(g_{a}:=p_{i}\); \(g_{b}:=p_{i+1}\); \(g_{c}:=g\); \(g_{d.x}:=0\); \(g_{d.y}:=g\);
4.if(SegSegInt (\(g_{a},g_{b},g_{c},g_{d}\)) = 1)then
5.\(count:=count+1\);
6.endif
7.if(mod(_count_, 2) = 1)then return 1;
8.else return 0;
9.endif
10.endfor
```  
**Algorithm 2**PtInPy(point \(g\), polygon \(P\))  
Algorithm 3 is the SqrInPy algorithm. It is a square-in-polygon algorithm whose inputs are a square \(S=\{s_{0},s_{1},\ldots,s_{4}\}\) and a polygon \(P=\{p_{0},p_{1},\ldots,p_{n}\}\). This algorithm is used to evaluate the space-overlap relationship between square \(S\) and polygon \(P\). Applying it will result in a value of 0, 1, or 2, representing that \(S\) is an inner square of \(P\), \(S\) is square intersecting with \(P\), or \(S\) is an outer area of \(P\). Lines 1 to 6 are used to calculate how many points of \(S\) are inner points of \(P\), which is where PtInPy is applied, and the _count_pt_ variable is used to count the number of inner points. Lines 7 to 18 are used to count the intersections between \(S\) and \(P\), which is where SegSegInt is applied, and _count_edge_ is used to count the number of intersections. Lines 19 to 22 are used to evaluate the coverage relationships between the square \(S\) and polygon \(P\). If the four vertices of square \(S\) are all outer points of polygon \(P\) (i.e., _count_pt_ = 0) and the four edges of \(S\) and \(n\) edges of the polygon do not intersect (i.e., _count_edge_ = 0), square S is an outer square of polygon \(P\). On the other hand, if all four vertices of square \(S\) are inner points of polygon \(P\) (i.e., _count_pt_ = 4) and the four edges of square \(S\) and \(n\) edges of the polygon do not intersect (i.e., _count_edge_ = 0), square \(S\) is an inner area of polygon \(P\). Otherwise, \(S\) intersects with polygon \(P\). Algorithm 4 is the RectOfPy algorithm. It is a rectangle-of-polygon algorithm whose input is a polygon \(P=\{p_{0},p_{1},\ldots,p_{n}\}\).