# B-Spline Curve Fitting of Hungry Predation Optimization on Ship Line Design
## 2 Related Works  
### B-Spline Theory Knowledge  
This section refers to the bibliography [23; 24]. The knot vector \(U\) consists of the non-decreasing parameter \(u_{i}\), \(U\): \(u_{0}\leq u_{1}\leq\cdots\leq\ u_{n+\rho+1}\), where the dimensions and values of the initial knot vector are random under certain constraints. After that, they will be adjusted with each iteration. It will be introduced in detail in Section 3. So far, B-spline basis function \(N_{i,\rho}(x)\) can be solved, as shown in Formula (1) and (2),  
\[\begin{split} N_{i,0}(x)=1,&\ u_{i}\leq x\leq u_{i+1 }\ (i=0,\ \ldots,\ n)\\ & 0,\ \ \text{other}\\ N_{i,\rho}(x)=&\frac{x-\ u_{i}}{u_{i+\rho}-u_{i}}N_{i, \rho-1}(x)+&\frac{u_{i+\rho+1}-x}{u_{i+\rho+1}-u_{i+1}}N_{i+1, \rho-1}(x)\end{split} \tag{1}\]  
where the first subscript \(i\) represents the sequence number, and the second subscript \(\rho\) represents degree (order \(\rho+1\)) of curve.  
Inappropriate degree may lead to the fitting curve cannot meet the accuracy requirement. Designers prefer to use piecewise low degree curves to describe complex curves, and they do not want a curve to be divided into too many segments. Because the cubic curve is not only a plane curve with inflection point, but also the lowest degree of spatial curves, it is widely used [24].  
A polynomial B-spline curve of degree \(\rho\) (or order \(\rho+1\)) is a piecewise polynomial curve given by  
\[p(x)=\sum_{i=0}^{n}d_{i}N_{i,\rho}(x)\quad x\in[0,\ 1] \tag{2}\]where \(d_{i}\) is the control point of the curve and \(N_{i,\rho}(x)\) is the \(\rho\)-degree-normalized B-spline basis function.  
According to Formula (3), it is necessary to obtain the control point \(d_{i}\) to realize the curve fitting, and the solution of \(d_{i}\) adopts the standard least square method and endpoint constraints. Interpolate the first and last data points \(P_{0}=p(0)\), \(P_{m}=p(1)\), and other data points \(P_{i}\) (\(i=1,\,2,\,\cdots,\,m-1\)) are approximated by the least-squares minimization method.  
The given data points are parameterized by the normalized accumulation chord length, as shown in Formula (4),  
\[x_{0}=x_{0}^{*}=0\] \[x_{i}^{*}=x_{i-1}^{*}+|\Delta P_{i-1}|\quad i=1,\,2,\,\cdots,\,m \tag{4}\] \[x_{i}=\frac{x_{i}^{*}}{x_{m}^{*}}\]  
where \(x_{i}\) is the parameter value corresponding to the current data point, and \(\Delta P_{i\,\,-\,1}\) is the forward difference vector, \(\Delta P_{i-1}=P_{i}-P_{i-1}\).  
The objective function is the square difference between each data point and the corresponding point on the curve fitted according to the new knot vectors obtained by HPA in the previous iteration, as shown in Formula (5). Then we can get Formula (7) through the transformation of Formula (6).  
\[f=\sum_{i=1}^{m-1}\,[\,P_{i}\,-\,p(x_{i}\,)\,]^{2} \tag{5}\]  
Let  
\[r_{i}=P_{i}-P_{0}N_{0,\rho}(x_{i})\,\,-\,P_{m}N_{n,\rho}(x_{i})\quad i=1,\,2, \cdots,\,m-1 \tag{6}\]  
Then,  
\[f=\sum_{i=1}^{m-1}\,[r_{i}-\sum_{j=1}^{n-1}d_{j}N_{j,\rho}(x_{i})]^{2} \tag{7}\]  
The \(L\)-th derivative of it is shown in Formula (8), in order to minimize the objective function \(f\), the derivative of \(n-1\) control points \(d_{j}\) needs to be 0, and then the final least-square fitting in Formula (9) can be obtained to solve the control point \(d_{j}\) in the current number of iterations.  
\[\frac{\partial\,f}{\partial d_{L}}=\sum_{i=1}^{m-1}[-2r_{i}N_{L,\rho}(x_{i})+2 N_{L,\rho}(x_{i})\,\sum_{j=1}^{n-1}d_{j}N_{j,\rho}(x_{i})] \tag{8}\]  
\[\sum_{j=1}^{n-1}(\sum_{i=1}^{m-1}\,N_{L,\rho}(x_{i})N_{j,\rho}(x_{i}))d_{j}= \sum_{i=1}^{m-1}r_{i}N_{L,\rho}(x_{i})] \tag{9}\]  
According to the obtained basis functions \(N_{i,\rho}(x)\) and control points \(d_{j}\), they are brought into Formula (3) to complete the curve fitting.