Curve fitting algorithm - P.J. Schneider

The main ideas of the algorithm

• Step 1: Given \(points=\{(x_1,y_1), (x_2,y_2),\dots, (x_n,y_n)\}\), generate a Bezier \(C\) with parameters \(\hat{t_1},\hat{t_2},\varepsilon\) respectively the left tangent, right tangent, and the allowable deviation.

• Step 2: Compute \(\text{error}\) is the sum of errors of the curve \(C\) when fitting with the \(points\)

  • If \(\text{error} < \varepsilon\). \(C\) is found, algorithm stops.

  • Otherwise, split the \(points\) at \(M(x_M,y_M)\) which is the furthest point to \(C\), then recursively generate \(C_1,C_2\) that fit to 2 new set of points: \([(x_1,y_1) \dots (x_M, y_M)]\) and \([(x_M, y_M) \dots (x_n,y_n)]\).

Some important notes

1. For ease of calculation, we use the curve calculation formula with parameter \(t\): \(Q(t) = \sum_{i=0}^nV_iB_i^n(t), \quad t \in [0,1]\)

2. For 3rd degree Bezier curves with control points \(P_1, P_2,P_3,P_4\) then the tangent to the curve at the endpoints \(P_1\) and \(P_2\) lies on the line containing the segment \(P_1P_2\) and the line contains the segment \(P_3P_4\). This is shown through the formula:

$$\displaystyle \frac {dQ}{dt} = Q^{\prime}(t)=n\sum_{i=0}^{n-1}(V_{i+1} - V_i)B_i^{n-1}(t)$$

Then, we can compute \(P_2=\alpha_1\hat{t_1}+P_1\) and \(P_3=\alpha_2\hat{t_2}+P_4\) with \(\hat{t_1}, \hat{t_2}\)respectively are tangent vectors at \(P_1\) and \(P_4\)

3. So fitting a curve with a set of points is essentially finding the appropriate value of \(\alpha_1, \alpha_2\). The details for calculation have been described quite thoroughly in the paper from page 618 to page 620, so I won't write it again. The implementation of this part is in the generateBezier function, you can refer to the source code section.

4. The remaining thing is to calculate the distance from a point \(P\) to the curve \(C\), with parametric equation \(Q(t)\):

   

I borrowed the drawing from the paper. In order to calculate the distance from \(P\) to \(Q(t)\) which means we need to calculate \(dist = ||P-Q(t)||\). Thus, curve fitting means we need to minimize the distance of all points in the set \(points\) to \(Q(t)\): \(\displaystyle \sum_{i=1}^n ||P_i - Q(t_i)||\), with \(t_i\) is the value of the accordant parrameter of \(P_i\). To simplify, we find the minimum of the sum of squared distances of all points in the set \(points\) to the curve \(C\): \(\displaystyle S=\sum_{i=1}^n[P_i-Q(t_i)]^2\)

5. In order to calculate \(t_i\), wwe approximate it by calculate the rate off its length over the sum of lengths of all segments. Then we try to update \(t_i\) by solving the equation\([Q(t_i)-P_i](Q^{\prime}(t_i)) = 0\) using Newton-Ralphson method with \(\displaystyle t_i \leftarrow t_i - \frac {f(t)}{f^{\prime}(t)}\).