# Analytical Solution for the Problem of Point Location in Arbitrary Planar Domains
## 7 Application to Bezier Curves  
Most planar domains can be defined by closed splines or other arbitrary curve segments, delimited by two extreme (anchor) points and some control points in a parametric way, which is most frequently of a polynomial nature.Each segment can however be treated the same way as was demonstrated earlier for linear and circular segments. For example, Bezier curves of order \(n\) in the complex plane can be defined by:  
\[B_{n}(t)=\sum_{k=0}^{n}t^{k}\Bigg{(}\frac{n!}{(n-k)!}\sum_{i=0}^{k}\frac{(-1)^ {i+k}z_{i}}{i!(k-i)!}\Bigg{)} \tag{60}\]  
where \(z_{i}\) are the control points, starting at \(z_{0}\) and ending at \(z_{n}\) (the anchor points), and with \(0\leq t\leq 1\). Segments are described by polynomials, making it easy both to differentiate and find roots, except for higher orders (like 5, 6, or more), and in that case, it can represent a challenge for analytical approaches, although numerical approaches are always possible. Bezier curves can also be expressed in the more compact notation:  
\[B_{n}(t)=\sum_{i=0}^{n}\binom{n}{i}(1-t)^{n-i}t^{i}z_{i},\,0\leq t\leq 1 \tag{61}\]  
from which follows an example of a Bezier segment of the \(3^{\text{rd}}\) order, which is one of the most commonly used, thus, representative of many challenges in computational geometry:  
\[B_{3}(t)=(1-t)^{3}z_{0}+3(1-t)^{2}tz_{1}+3(1-t)t^{2}z_{2}+t^{3}z_{3} \tag{62}\]  
or, in full expansion:  
\[B_{3}(t)=(3z_{1}-z_{0}-3z_{2}+z_{3})t^{3}+3(z_{0}-2z_{1}+z_{2})t^{2}+3(z_{1}- z_{0})t+z_{0}. \tag{63}\]As described earlier, detecting the NRA crossing of such a segment requires the solution of \(B_{3}(t)=0\), which would yield up to 3 results for \(t\) in the \([0,+1]\) interval. If less than 3 NRA intersections occur, this means that some solutions for \(t\) are complex, and are to be discarded. To determine the sense of growing at the intersection points with the NRA, the derivative of \(B_{3}(t)\) in order to \(t\) is required, and that too is a direct operation easily allowed by the polynomial representation of the curve segment:  
\[\frac{\mathrm{d}B_{3}(t)}{\mathrm{d}t}=3(3z_{1}-z_{0}-3z_{2}+z_{3})t^{2}+6(z_{ 0}-2z_{1}+z_{2})t+3(z_{1}-z_{0}). \tag{64}\]  
Figure 16 shows a region defined by a cubic Bezier curve and two linear segments. In this case, the Bezier anchor points are \(z_{0}=(0,0)\) and \(z_{3}=(2,1)\) and the two control points are \(z_{2}=(0,-1)\) and \(z_{3}=(2,1)\). The two linear segments are \(\overline{z_{3}z_{4}}\) and \(\overline{z_{4}z_{0}}\). Points \(a_{1}=(0.9,0.6)\) and \(a_{2}=(1.1,0.4)\) will be tested but only \(a_{1}\) is included in the region. To test points \(a_{1}\) and \(a_{2}\), the procedure seems to require the adjustment of the \"vertices\" values reported to each testing point and calculate the new resulting polynomials. Actually, that turns out unnecessary in the parametric form because the new polynomial only changes by an offset, and the generic expression (63) simply becomes \(B_{3}(t)\gets B_{3}(t)-a_{i}\), where \(a_{i}\) is the point being tested. An additional relevant aspect for computational purposes is that the expression for the Bezier polynomial derivative (64) remains the same whatever the testing point \(a_{i}\), which saves computation resources when testing the inclusion of many different points for the same region. The generic equations to test the NRA crossing and contributions (\(I_{C}\)) for a given \(a_{i}=(a_{x_{i}},a_{y_{i}})\) are:  
\[ \begin{cases}x_{B_{3}}=8t^{3}-12t^{2}+6t-a_{x_{i}}\\ y_{B_{3}}=10t^{3}-15t^{2}+6t-a_{y_{i}}\\ \frac{\mathrm{d}y_{B_{3}}}{\mathrm{d}t}=30t^{2}-30t+6\end{cases} .\]  
To solve the problem for this particular situation, the procedure is implemented as follows:  
1. Find the roots of \(y_{B_{3}}=10t^{3}-15t^{2}+6t-a_{y_{i}}\);
2. Test whether the found roots satisfy the condition of NRA intersection, that is, \(x_{B_{3}}=8t^{3}-12t^{2}+6t-a_{x_{i}}\approx 0\);
3.