## Wednesday, November 11, 2015

### Easier Bezier by 2nd derivative smoothing

So supposing you have n points on the plane with n greater than or equal to 4 and you want to find a smooth curve through them, you could do a n-degree bezier curve through them but that takes exponential time with respect to n to calculate or you could use bezier splines of a lesser degree but if you use , say, quadratic bezier splines through the n points directly there is a smoothness problem... The approach I'll outline below is to generate with a formula the 2*n-1 "halfway" points between known points then use quadratic bezier curves to interpolate but the way the "halfway" points are calculated gives a smooth final result...

So first we take our n points and label them A(2*(j)-1) for j from 0 to n, and from here on call them A(i)... Then we use this formula:
This formula is saying that the 2nd derivative by divided differences at a point should be the average of the 2nd derivative at the point before it and the point after it...

Now here is a python program to figure out what the i values should be in the formula above to get the right number of equations for the number of new "halfway" points :

n=7
d = 1.0*(2*n-6)/(n-2)
for i in range(0, n-1):
print(round(3+i*d))

For n=4 we get:
3,4,5

For n = 5 an odd number of points, we need 4 equations for the 4 in between points so we make the i's using the program::
3,4,6,7

For n = 6 there are 5 in between points we need equations for so we make the i's:
3,4,6,8,9

For n = 7:
3,5,6,8,9,11

For n = 6 we know the six points A1, A3, A5, A7, A9,A11 and we want to know A2, A4, A6, A8, A10 so we use the i values from the program {3,4,6,8,9} and get five equations to solve:

Then the third step is to use these newly generated points to compute the quadratic Bezier paths between odd labeled points (I used a graphics program to manually draw the Beziers so they don't go exactly through the center of each point but mathematically they would)...

Compare this to using quadratic Beziers directly...

And there are some issues using just Beziers with even number of points about how exactly to divide the curve into quadratics because you need groups of 3 points for quadratic Beziers...