# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 2 Related Work
### Winding Number Based Approaches  
The problem of non-simple polygons (self-intersecting) has nonetheless been practically solved with algorithms based on the winding number [7], also named nonzero-rule algorithms, which have been refined and even made as efficient as the ray-crossing approach [14]. Its formulation, based on the sum of all the oriented angles with a center in the test point and delimited by each pair of successive vertices of the polygon, allows to obtain the winding number around a point (the number of times a closed curve winds around a given point in the positive sense), and then conclude whether the point is inside or outside the region. If \(\alpha_{1},\alpha_{2},\ldots,\alpha_{M}\) are the \(M\) oriented angles defined by the testing point and the \(M\) segmented defined with the \(M\) vertices of a polygon, the winding number is calculated by \(W_{N}=\frac{1}{2\pi}\sum_{i=1}^{M}\alpha_{i}\). If \(W_{N}\) is equal to zero, then the number of winds of the polygon around the point is zero, meaning that the point is \"outside\" the polygon. Any other value for \(W_{N}\) will indicate that the point is \"inside\" the polygon. Figure 4 illustrates the geometric principle of the procedure for a simple polygon. However, the traditional winding number-based algorithms may be ambiguous if the point lies on the boundary and nearly all implementations show some degree of false positives and missed detections, as demonstrated by [PERSON] in [18]. The technique described generically in Figure 4 is often seen in the literature as the calculation of the winding number contribution of each linear segment (\(\overline{p_{1}p_{2}}\)) relative to a point \(a\), where all of the contributions are added up. Mathematically, the procedure is simple, as presented, for example in [19], and can be easily understood as the calculation of the winding number contribution of that segment relative to the given test point \(a\):  
\[ \begin{cases}\vec{u}=p_{1}-a\\ \vec{v}=p_{2}-a\\ \alpha=\text{atan2}(\vec{u}\times\vec{v},\vec{u}\cdot\vec{v})\end{cases} . \tag{1}\]  
Demonstration of (1) is straightforward because \(\vec{u}\times\vec{v}=|\vec{u}||\vec{v}|\sin(\alpha)\) and \(\vec{u}\cdot\vec{v}=|\vec{u}||\vec{v}|\cos(\alpha)\). In this context \(\vec{u}\times\vec{v}\) is actually supposed to mean the third component of the actual cross product \((u_{x},u_{y},0)\times(v_{x},v_{y},0)\). Possible alternative notations would be to replace \(\vec{u}\times\vec{v}\) in (1) by \(\det\ \left[\vec{u}^{T}\ \ \vec{v}^{T}\ \ \ \ \mathbb{1}^{T}\right]\,\) where \(\mathbb{1}=\ \left[\ 1\ \ \ 1\ \ \right]\,\) or \((\vec{u}\times\vec{v})_{3}\) or, of course, \((u_{x}v_{y}-u_{y}v_{x})\). When a point falls over the boundary of a region, more than one interpretation may arise. An example of that occurs in Figure 5, where two adjacent regions \(R_{1}\) and \(R_{2}\) (delimited by different shades and without the border lines being drawn to visually enhance the effect) seem to share a point \(a\) because it falls precisely on the boundaries of  
Figure 4: Algorithm based on the winding number. If \(\sum_{i}\alpha_{i}=0\), then the testing point (\(b\) in this case) is outside the polygon. the regions. This raises the question of whether point \(a\) belongs to both regions, to only one of them, or neither of them! The possibility of belonging to neither of the regions must be discarded since \(a\) lies in a area covered by both regions altogether, seeming absurd to affirm that \(a\) does not belong to neither of the regions and at the same time belonging to their union. So, there remains the possibility of belonging to only \(R_{1}\) or \(R_{2}\), or both at the same time. This is where the variation of interpretation can take place. If regions are analyzed independently, and using the winding number approach, any conclusion (belonging or not to \(R_{1}\) or \(R_{2}\)) can be taken depending on the circulation sense of the polygonal lines, as described next.