# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 5 NRA Crossing in Parametric Paths
### Optimizing Algorithm 3  
Algorithm 3 on the preceding page can be computationally alleviated by avoiding unnecessary divisions in case the NRA intersection does not occur. Indeed, as required by expression (42), for NRA intersection to occur we must have the following: \(0\leq\frac{y_{1}}{y_{1}-y_{2}}\leq 1\). In other words, if either \(\frac{y_{1}}{y_{1}-y_{2}}>1\) or \(\frac{y_{1}}{y_{1}-y_{2}}<0\), then the NRA intersection does not occur, and no more calculations need to be performed. So, a few comparisons (3 at most) can be made before asserting the need to perform the division to find the actual \(t_{c}\) of NRA intersection. Since \(y_{1}-y_{2}=\Delta y\), consider the following:  
\[\frac{y_{1}}{\Delta y}<0\Rightarrow(\Delta y>0\wedge y_{1}<0)\vee(\Delta y<0 \wedge y_{1}>0) \tag{46}\]  
\[\frac{y_{1}}{\Delta y}>1\Rightarrow(\Delta y>0\wedge y_{2}>0)\vee(\Delta y<0 \wedge y_{2}<0), \tag{47}\]  
which can be combined. We are allowed to state that there is no NRA intersection if the following occurs:  
\[ \begin{cases}\Delta y>0\wedge(y_{1}<0\lor y_{2}>0)\\ \Delta y<0\wedge(y_{2}<0\lor y_{1}>0)\end{cases} \quad\Rightarrow\star\infty. \tag{48}\]  
Hence, just before line 11 of Algorithm 3 a few lines could be added to optimize the procedure, demonstrating also that at most 3 comparisons are needed to conclude whether there is NRA intersection or not before calculating \(t_{c}=Y_{1}/\Delta Y\), as proposed next:  
```
if\(\Delta Y>0\)then if\(Y_{1}<0\)or\(Y_{2}>0\)then  continue //no NRA intersection endif else if\(Y_{2}<0\)or\(Y_{1}>0\)then  continue //no NRA intersection endif endif
11:\(t_{c}\leftarrow\frac{Y_{1}}{\Delta Y}\)
```  
Figure 10: Multi-ring polygons as used in GIS contexts. The orientations are indicative, but appropriate relative senses must be ensured to correctly represent, for example, a polygon with a “hole”. Previous expressions can be further optimized because when they are reached, it is already known that \(\text{sgn}(Y_{1})\
eq\text{sgn}(Y_{2})\). Therefore, \(Y_{1}<0\lor Y_{2}>0\) is equivalent to only one of them, e.g., \(Y_{1}<0\). A similar reasoning applies to the \"else\". This further reduces the number of comparisons from 3 to 2. In case there is intersection (i.e., the previous tests concluded that there may be a NRA intersection because \(0\leq t_{c}\leq 1\)), it is then necessary to calculate its precise value to test the second requirement of expression (42), that is, check the condition \(t_{c}(x_{1}-x_{2})\geq x_{1}\), which at first glance seems unavoidable to calculate through the division. But, actually, that division operation can be avoided and replaced by two multiplications and a comparison, as is shown next: being \(x_{1}-x_{2}=\Delta x\) and \(t_{c}\Delta x\geq x_{1}\Leftrightarrow\frac{y_{1}}{\Delta y}\Delta x\geq x_{1}\), if \(\Delta y>0\) then, for NRA crossing, we need to have: \(y_{1}\Delta x\geq x_{1}\Delta y\), otherwise, we need to have the following: \(y_{1}\Delta x\leq x_{1}\Delta y\). The conclusion is summarized by expression (49):  
\[ \begin{cases}\Delta y>0\wedge y_{1}\Delta x\geq x_{1}\Delta y\\ \Delta y\leq 0\wedge y_{1}\Delta x<x_{1}\Delta y\end{cases} \Rightarrow\#\text{o}. \tag{49}\]  
This last simplification not only avoids the mathematical division butalso allows the algorithm to fully operate in integer arithmetic representation, which would improve its usage in an approach based purely on the integer representation of points/vertices. Yet, in line 17, Algorithm 3 still requires to check whether \(t_{c}\) is equal to 0 or to 1 to conclude if the \"crossing\" is actually a \"touching\", which would imply an adjustment on the intersection counter. But that checking turns out redundant because those cases correspond to \(y_{1}=0\) or \(y_{2}=0\), that is, there is no need to calculate \(t_{c}\) for those cases either. In summary, the algorithm in its full extension and covering all these optimizations, is detailed as Algorithm 4 on the next page.