Least squares by tolerance?

Question

In the documentation for MicroStation (https://docs.bentley.com/LiveContent/web/OpenBuildings%20Designer%20Help-v3/en/GUID-2B6B090B-CEC2-C255-8A0B-425F1075A9EE.html), there exists a method for creating B-splines curves using a method called "Least squares by tolerance" where the user supplies a "tolerance" i.e. a maximum deviation from the input polygon that the B-Spline may lie.

How would this be implemented? I've done a lot of research and have only found a method on Least squares where the number of control points is specified, but not a tolerance.

Not necessarily specfically, but what would a least squares by tolerance algorithm look like?

Answer 1

The "By tolerance" LS fitting actually works like this:

1. Perform LS fitting with a B-spline of single segment. Denoting the output curve as $C(t)$.
2. Compute the error of each data point. $Err_i= ||P_i - C(t_i)||$ where $P_i$ are the data points and $t_i$ the parameters, then compute the maximum error.
3. If the maximum error is smaller than the tolerance, you are done. If not, increase the number of segments (and therefore the number of control points) and go back to step 1.

Several issues to note:

• Make sure that the number of control points is always smaller than the number of data points during the iterations. If they become equal, then you will be doing interpolation, instead of LS fitting.
• How do you increase the number of segments is a matter of choice. You can increase the number of segments one by one, which will make the whole iteration converge slowly but will never produce a B-spline curve with more control points than necessary. Alternatively, you can also double the number segments each time for a faster convergence and accept the fact that the final B-spline curve might have too many control points.
• Also, the error vector computed from step 2 is typically not orthogonal to the curve produced by the LS fitting. So, the maximum error obtained this way is typically bigger than the "true" maximum deviation between the data points and the B-spline curve. There is a technique that will adjust the parametrization to make the error vector become more orthogonal to the output curve. This technique is described in "Intrinsic parametrization for approximation, by J. Hoschek, published in CAGD Vol5, 1988.