# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 5 NRA Crossing in Parametric Paths
### NRA Crossings and Their Sense for Linear Segments  
What we seek to detect is whether there is an intersection and what is its sense. And this is straightforward to calculate after (38), which can be expanded into:  
\[ \begin{cases}\Re\{z\}=x=x_{1}+t(x_{2}-x_{1})&\Leftarrow 0\leqslant t\leqslant 1 \\ \Im\{z\}=y=y_{1}+t(y_{2}-y_{1})&\Leftarrow 0\leqslant t\leqslant 1\end{cases} . \tag{41}\]  
A NRA intersection occurs at some point \(z_{c}\) when \(\Im\{z_{c}\}=0\) and \(\Re\{z_{c}\}\leqslant 0\) in \(z_{c}=z_{1}+t_{c}(z_{2}-z_{1})\), \(0\leqslant t_{c}\leqslant 1\), i.e., intersection occurs for the value \(t_{c}\) that verifies:  
\[\left\{ \begin{array}{l}y_{1}+t_{c}(y_{2}-y_{1})=0\\ x_{1}+t_{c}(x_{2}-x_{1})\leqslant 0\end{array} \right._{\Leftrightarrow}\left\{ \begin{array}{l}t_{c}=\frac{y_{1}}{y_{1}-y_{2}}\\ t_{c}(x_{1}-x_{2})\geqslant x_{1}\end{array} \right.. \tag{42}\]  
Notice that the case \(y_{1}=y_{2}\) represents a horizontal segment, and \"intersection\" only occurs for \(y_{1}=y_{2}=0\). However, that is not actually an intersection of the NRA, as explained later, and this special situation is to be discarded early in the algorithms (also to avoid the division by 0). Apart from that case, if a valid \(t_{c}\) is found, then it is necessary to determine the sense of the NRA crossing, and that is easily verifiable by the derivative of the imaginary component \(\Im\{z\}\) in relation to \(t\). If the derivative is positive for that value of \(t_{c}\), it means that the \(y=\Im\{z\}\) component is increasing with \(t\), therefore the path segment is passing from \(Q3\) to \(Q2\), or +\(\phi\), that is, there is a contribution of \(-1\) to the intersection counting (\(I_{C}\)), or \(+1\) for the reverse case (\(Q2\) to \(Q3\), or +\(\phi\)). This can be formalized as:  
\[I_{C}=-\operatorname{sgn}\left(\frac{\operatorname{d}y}{\operatorname{d}t} \Big{|}_{t=t_{c}}\right). \tag{43}\]  
For linear segments, the previous expression is constant for any point of the segment where the NRA crossing might occur:  
\[I_{C}=-\operatorname{sgn}(y_{2}-y_{1})=\operatorname{sgn}(y_{1}-y_{2}). \tag{44}\]  
If, by chance, the testing point happens to be an intersection point of the polygon boundary with the NRA, either along the path segment (\(t_{c}\
eq 0\) and \(t_{c}\
eq 1\)) or strictly on a vertex (\(t_{c}\) is 0 or 1), that can be promptly detected because its real coordinate would be zero: \(x_{1}+t_{c}(x_{2}-x_{1})=0\). This indicates that the point is over the boundary, and a decision can be made immediately without further calculations. Formally: if \(x_{1}=t_{c}(x_{1}-x_{2})=t_{c}\Delta x\), then the point is on the boundary, and can be dispatched earlier in the algorithm. There are also the particular cases of \(t_{c}=0\) or \(t_{c}=1\); these represent the cases where the segment starts or ends exactly on the NRA (-\(\varphi\) or -\(\lambda_{0}\)). In those cases, this means that another segment starts or ends there too! To leave the contributions separate, but allowing them to add up or cancel, for those cases, the intersection contribution calculated above should be halved, that is, a \(\pm 0.5\) contribution for segments that originate or end on the NRA is to be applied. In other words, each crossing of the NRA can be accounted with \(\pm 1\), but reaching or leaving it can be accounted as a half-crossing, or \(\pm 0.5\). Formally, this can be stated as in (45):  
\[t_{c}=0\lor t_{c}=1\Rightarrow I_{C}=-0.5\operatorname{sgn}\left(\frac{ \operatorname{d}y}{\operatorname{d}t}\Big{|}_{t=t_{c}}\right). \tag{45}\]  
Figure 9 illustrates the situation of \(I_{C}\) values for several testing points (\(a_{1},a_{2},\ldots,a_{9}\)) in a polygonal self-intersecting region; the associated table details the partial and total values of NRA intersection counting. At each case (point \(a_{i}\)), the imaginary axis would be a vertical line that crosses the enclosed domain exactly at each of the \(a_{i}\) points.