# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 5 NRA Crossing in Parametric Paths
### Universal Algorithm for Arbitrary Polygons  
All of the previous procedures are integrated in Algorithm 3 on the following page, which shows all the steps to test polygonal inclusion of any point \(a\) on any polygon with \(M\) vertices (for any \(M>0\), but only \(M>2\) is really meaningful), normal or self-intersecting.  
The computational cost of Algorithm 3 is \(\mathcal{O}(n)\), and the arithmetic operations involved are only sums (or subtractions) and at most \(M\) floating point divisions per polygon, although optimizable, as described further.  
Figure 9: Contributions of NRA intersections/touchings on the left side of nine example test points. The sense of NRA reaching/crossing is relevant for the final sum. Since the imaginary axis would lie over each \(a_{i}\) point, the numbers in the table indicate the \(I_{C}\) partial and total values, i.e., the counting of intersections (crossings) of the NRA. For example, the total down \(I_{C}\) for \(a_{6}\) is given by summing all downward NRA intersections at its left: \(+3=+1+0.5+0.5+1\) and, similarly, for the total up \(I_{C}\), the count is \(-2=-0.5-1-0.5\). The net total is \(I_{C}=+1\), hence \(a_{6}\) is inside. Curiously, the result for \(a_{7}\) is \(I_{C}=+2\), that is, we could consider that \(a_{7}\) is inside “twice”, which is graspable from the figure!  
```
1:\(a=(a_{x},a_{y})\), \(P_{n}=(x_{n},y_{n})\) for \(n=1,2,\ldots,M\)
2:\(P_{n}\gets P_{n}-a\) for \(n=1,2,\ldots,M\)
3:\(I_{\mathcal{C}}\gets 0\)//NRA Intersection counter
4:for\(n=1\)to\(M\)do
5:\(Y_{1}\gets y_{n}\) ; \(Y_{2}\gets y_{(n\bmod M)+1}\)
6:\(X_{1}\gets x_{n}\) ; \(X_{2}\gets x_{(n\bmod M)+1}\)
7:if\(\operatorname{sgn}(Y_{1})==\operatorname{sgn}(Y_{2})\)then
8:continue //no NRA crossing: horizontal segment or segment entirely in one quadrant. Jump to next segment.
9:endif
10:\(\Delta Y\gets Y_{1}-Y_{2}\)
11:\(\Delta X\gets X_{1}-X_{2}\)
12:\(t_{c}\leftarrow\frac{Y_{1}}{\Delta Y}\)
13:if\(t_{c}\Delta X==X_{1}\)then
14:return true //point \(a\) is on the boundary (included)
15:endif
16:if\(t_{c}\geq 0\)and\(t_{c}\leq 1\)and\(t_{c}\Delta X\geq X_{1}\)then
17:\(I_{P}\leftarrow\operatorname{sgn}(\Delta Y)\)
18:if\(t_{c}==0\)or\(t_{c}==1\)then
19:\(I_{P}\gets I_{P}\times 0.5\) //touch NRA only
20:endif
21:\(I_{\mathcal{C}}\gets I_{\mathcal{C}}+I_{P}\)
22:endif
23:endfor
24:if\(I_{\mathcal{C}}\
eq 0\)then
25:return true //point \(a\) is included
26:else
27:return false //point \(a\) is not included
28:endif
```  
**Algorithm 3**Universal inclusion test in arbitrary polygons  
In Algorithm 3, the points on the border, including vertices, are considered inside the polygon, but, if wanted otherwise, this can be easily modified to exclude them. It can be done either with an optional initial checking for \(a\) being one of the vertices or during the normal flow of the algorithm after test from line 12 that results from the NRA crossing conditions in expression (42). The decision on line 13 of Algorithm 3 could be set to **false** if the point on the boundary is defined as being outside.  
Notice also that the apparent risk of division by zero in line 11 of the algorithm never occurs because of early analysis in line 6 of the algorithm; indeed, if \(Y_{1}==Y_{2}\), we also have \(\operatorname{sgn}(Y_{1})==\operatorname{sgn}(Y_{2})\) and the algorithm skips to the next segment since there is no contribution of the current linear segment to the value of \(I_{\mathcal{C}}\). Illustration of the functionality and results of Algorithm 3 can be found in the GitHub repository indicated earlier.