# Optimal approximation of spline curve using linear interpolation

I have a parametric cubic spline which I need to draw in graphics. I am restricted to using a set of lines to draw this, and for performance reasons I need as few lines as possible. So I need an adaptive sampling scheme with small steps in high curvature intervals and large steps in straight intervals.

I found a description for adaptive stepsize in the Runge-Kutta-Fehlberg method which matches my requirements in a sense, but the use case is too different to make use of it.

In essence, I need the spacings between N number of points along a parametric spline which minimizes the error between a linearly interpolated curve between those points and the spline from which those points originate.

Update: The spline may contain many knots in straight segments, so it is necessary to drop original points.

• If you really want to minimize the number of lines, you should be using lines whose end-points don't lie on your curve. Search for "polyline approximation". There is a vast amount of literature on the subject. – bubba Jun 4 '16 at 2:48
• @bubba, that makes sense, I will investigate if such methods exist for splines. – Petter Kvalvaag Jun 21 '16 at 12:26

Finding the optimal spacing of N points that minimizes the error to the original spline might not be your best shot in achieving the best rendering performance as the computation cost for finding the optimal spacing of these N points might be too high and you will be better off to simply sample $2N$ points uniformly.

If you really would like to use an adapative sampling scheme, here is what I would suggest. This is not the same as finding the optimal spacing of N points to minimize the error to the original spline. Instead, this algorithm will find out a linear approximation of the spline where the error is smaller than a predefined value.

1) Suppose the parametric cubic spline is defined over knot values $(0,t_1,t_2,....,1)$ where we have a cubic polynomial curve in between each two knot values. We also define a tolerance $\varepsilon$ representing the maximum deviation between the parametric cubic spline and the linear approximation

2) For $i$-th cubic polynomial segment (where t $\in [t_i,t_{i+1}]$), convert it into cubic Bezier form. Namely, find the 4 control points $P_0, P_1, P_2$ and $P_3$ with $P_0=C(t_i)$ and $P_3=C(t_{i+1})$.

3) Compute distances $d_1$ and $d_2$, which are the vertical distance from $P_1$ and $P_2$ to the line defined by $P_0$ and $P_3$. If both $d_1$ and $d_2$ are not greater than $\varepsilon$, then you only need to draw a single line segment from $P_0$ to $P_3$ for this cubic segment. Add $t_i$ and $t_{i+1}$ to your parameter array and proceed to the next cubic polynomial segment.

4) If either $d_1$ or $d_2$ is greater than $\varepsilon$, then split the Bezier curve at $u=0.5$ (where $u$ is the parameter of the cubic Bezier curve) using de Castljau algorithm and repeat step 3 for the two Bezier curves. Add $t=0.5(t_i+ t_{i+1})$ to the parameter array.

5) After finish processing all cubic polynomial segments, sort the parameter array in ascending order.

The advantage of this algorithm is that the final number of points in the linear approximation depends on how large the $\varepsilon$ you choose. If users had zoomed in very close to the spline, you can use a smaller $\varepsilon$ value to draw the spline in details. But if users is far away from the spline, then you can use a large $\varepsilon$ value, which will lead to fewer points for the linear approximation.

• Great stuff. Inserting points where necessary based on tolerance fits my use case even better. Regarding the comment on rendering performance; this spline does not regularly change during the scope of displaying it, so there is a lot to gain by computing an optimal line set for my application. – Petter Kvalvaag Jun 2 '16 at 7:30
• The reason I had originally formulated this problem as "N points that minimize the error" is that I believe it is the right approach when I need to drop whole straight segments (see updated question). I guess I can add that as another step in you proposed algorithm though. – Petter Kvalvaag Jun 2 '16 at 8:40
• If the spline could contain many straight cubic segments, then yes you should incorporate a final step to check if two consecutive line segments can be merged or not. Let us know whether the proposed algorithm works for you. – fang Jun 2 '16 at 17:40