CODEWITHSUNDEEP
pythongaussiansmoothing
Whisper
Whisper

Reputation: 23

Algorithm for generating smooth curves from incoming data points

I'm looking for an algorithm that smoothly interpolates points as they come in live.

For example, say I start with an array of 10 (x,y) pairs. I'm currently using scipy and a gaussian window to generate a smooth curve. However, what I can't figure out is how to update the smoothed curve in response to an 11th point generated at some future point (without completely redoing the smoothing for all 11 points).

What I'm looking for is an algorithm that follows the previous smooth curve up to the 10th (x,y) pair and also smoothly interpolates between the 10th and 11th pair (in a way that's similar to redoing the entire algorithm - so no sharp edges). Is there something out there that does what I'm looking for?

Upvotes: 2

Views: 1475

Answers (1)

Ricardo
Ricardo

Reputation: 590

I think you could make use of a Cubic Spline. Given a list of n points (x_1, y_1)..(x_n, y_n), the algorithm finds a cubic polynomial p_k between (x_k, y_k) and (x_{k+1}, y_{k+1}) with the following constraints:

  • polynomials p_k and p_{k+1} passes through the point (x_{k+1}, y_{k+1});
  • polynomials p_k and p_{k+1} have the same first derivative at (x_{k+1}, y_{k+1});
  • polynomials p_k and p_{k+1} have the same second derivative at (x_{k+1}, y_{k+1}).

Also, there are some boundary conditions, defined for the first and the last polynomial. I have used natural, which forces the second derivative to zero at the end of the curves.

The steps that you could apply are:

  1. Interpolate the first 10 points using the Cubic Spline.
  2. Assign the first derivative value at p_10 to a variable d.
  3. Run the Cubic Spline for p_10 and p_11, enforcing that the first derivative at p_10 is d and the second derivative at p_11 is zero.

From there, you can repeat the same steps for the remaining points.

This code will generate a interpolation for all points:

import matplotlib.pyplot as plt
import numpy as np
from scipy.interpolate import CubicSpline

height=4
n = 20
x = np.arange(n)
xs = np.arange(-0.1,n+0.1,0.1)
y = np.random.uniform(low=0, high=height, size=n)

plt.plot(x, y, 'o', label='data')
cs = CubicSpline(x, y)
plt.plot(xs, cs(xs), color='orange')
plt.ylim([0, height+1])

Interpolation for 20 points

Now, this code will interpolate the first 10 points, followed by another interpolation between points 10 and 11:

k = 10
delta = 0.001

plt.plot(x, y, 'o', label='data')
xs = np.arange(x[0], x[k-1]+delta, delta)
cs = CubicSpline(x[0:k], y[0:k])
plt.plot(xs, cs(xs), color='red')

d = cs(x[k-1], 1)

xs2 = np.arange(x[k-1], x[k]+delta, delta)
cs2 = CubicSpline(x[k-1:k+1], y[k-1:k+1], bc_type=((1, d), 'natural'))
plt.plot(xs2, cs2(xs2), color='blue')

plt.ylim([0, height+1])

enter image description here

Upvotes: 4

Related Questions