Find control point on piecewise quadratic Bezier curve

Question

I need to write a program to generate and display a piecewise quadratic Bezier curve that interpolates each set of data points (I have a txt file contains data points). The curve should have continuous tangent directions, the tangent direction at each data point being a convex combination of the two adjacent chord directions.

0.1 0, 
0 0,
0 5,
0.25 5,
0.25 0, 
5 0, 
5 5, 
10 5,
10 0, 
9.5 0

The above are the data points I have, does anyone know what formula I can use to calculate control points?

Answer 1

You will need to go with a cubic Bezier to nicely handle multiple slope changes such as occurs in your data set. With quadratic Beziers there is only one control point between data points and so each curve segment much be all on one side of the connecting line segment.

Hard to explain, so here's a quick sketch of your data (black points) and quadratic control points (red) and the curve (blue). (Pretend the curve is smooth!)

Look into Cubic Hermite curves for a general solution.

Answer 2

From here: http://blog.mackerron.com/2011/01/01/javascript-cubic-splines/

To produce interpolated curves like these:

You can use this coffee-script class (which compiles to javascript)

class MonotonicCubicSpline

# by George MacKerron, mackerron.com

# adapted from: 
# http://sourceforge.net/mailarchive/forum.php?thread_name=
# EC90C5C6-C982-4F49-8D46-A64F270C5247%40gmail.com&forum_name=matplotlib-users
# (easier to read at http://old.nabble.com/%22Piecewise-Cubic-Hermite-Interpolating-
# Polynomial%22-in-python-td25204843.html)

# with help from:
# F N Fritsch & R E Carlson (1980) 'Monotone Piecewise Cubic Interpolation', 
#   SIAM Journal of Numerical Analysis 17(2), 238 - 246.
# http://en.wikipedia.org/wiki/Monotone_cubic_interpolation
# http://en.wikipedia.org/wiki/Cubic_Hermite_spline

constructor: (x, y) ->
  n = x.length
  delta = []; m = []; alpha = []; beta = []; dist = []; tau = []
  for i in [0...(n - 1)]
    delta[i] = (y[i + 1] - y[i]) / (x[i + 1] - x[i])
    m[i] = (delta[i - 1] + delta[i]) / 2 if i > 0
  m[0] = delta[0]
  m[n - 1] = delta[n - 2]
  to_fix = []
  for i in [0...(n - 1)]
    to_fix.push(i) if delta[i] == 0
  for i in to_fix
    m[i] = m[i + 1] = 0
  for i in [0...(n - 1)]
    alpha[i] = m[i] / delta[i]
    beta[i]  = m[i + 1] / delta[i] 
    dist[i]  = Math.pow(alpha[i], 2) + Math.pow(beta[i], 2)
    tau[i]   = 3 / Math.sqrt(dist[i])
  to_fix = []
  for i in [0...(n - 1)]
    to_fix.push(i) if dist[i] > 9
  for i in to_fix
    m[i]     = tau[i] * alpha[i] * delta[i]
    m[i + 1] = tau[i] * beta[i]  * delta[i]
  @x = x[0...n]  # copy
  @y = y[0...n]  # copy
  @m = m

interpolate: (x) ->
  for i in [(@x.length - 2)..0]
    break if @x[i] <= x
  h = @x[i + 1] - @x[i]
  t = (x - @x[i]) / h
  t2 = Math.pow(t, 2)
  t3 = Math.pow(t, 3)
  h00 =  2 * t3 - 3 * t2 + 1
  h10 =      t3 - 2 * t2 + t
  h01 = -2 * t3 + 3 * t2
  h11 =      t3  -    t2
  y = h00 * @y[i] + 
      h10 * h * @m[i] + 
      h01 * @y[i + 1] + 
      h11 * h * @m[i + 1]
  y