Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given 3 pairs of coordinates, $x_1, y_1, x_2, y_2, x_3, y_3$, I need a function $y(x)$ that will return the $y$ coordinate of any $x$ coordinate between $x_1$ and $x_3$ (it can be assumed that $x_1 < x_2 < x_3$).
$y(x_1)$ must equal $y_1$, $y(x_2)$ must equal $y_2$, and $y(x_3)$ must equal $y_3$.

However, it must never return a $y$ coordinate that is larger than the largest of $y_1$, $y_2$, and $y_3$, or smaller than the smallest of $y_1$, $y_2$, and $y_3$. This is the part which I have not yet figured out how to do.

(This is not schoolwork. I'm writing an audio creation library, and these curves will be used to define volume over time.)

share|improve this question
1  
I don't think the 2nd and 3rd condition are compatible. I can't think of a quadratic curve bounded by [0,1]x[0,1] passing through (0,0), (0.5,0), (1,1). –  KennyTM Sep 5 '10 at 19:07
    
@KennyTM The 3rd condition was actually more of a preference than a requirement, so I removed it. –  Wallacoloo Sep 5 '10 at 19:18
add comment

2 Answers

up vote 1 down vote accepted

What you apparently want is a monotonic interpolation scheme. As mentioned already, fitting a single polynomial to your data will result in an interpolant that does not necessarily satisfy your constraints. Using a piecewise polynomial function (a function that has a different polynomial representation at each interval) should do a better job.

Classically, the most-used class of piecewise polynomial functions is the piecewise cubic Hermite interpolant, whose representation in an interval $[x_i,x_{i+1}]$ looks like

$y_i+y_i^{\prime}\left(x-x_i\right)+c_i\left(x-x_i\right)^2+d_i\left(x-x_i\right)^3$

where

$c_i=\frac{3s_i-2y_i^\prime-y_{i+1}^\prime}{x_{i+1}-x_i}$

$d_i=\frac{y_i^\prime+y_{i+1}^\prime-2s_i}{\left(x_{i+1}-x_i\right)^2}$

$s_i=\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$

and ${y_i^\prime,y_{i+1}^\prime}$ are the slopes (derivative values) of your interpolant at the corresponding points $(x_i,y_i)$, $(x_{i+1},y_{i+1})$.

Now, you will rightly ask, "how do I determine the $y_i^\prime$?" There are a number of schemes to do this: one of the most popular is the cubic spline, which imposes the additional constraint that the interpolant have two continuous derivatives. The problem with this approach is that there can still be extraneous wiggles in your interpolant.

One approach to ensure the monotonicity (i.e. the curve representing your data to fit against has no spurious wiggles) of your piecewise cubic Hermite interpolant is to use the Stineman scheme. The formula for computing slopes is a bit more elaborate, so I'll just have to refer you to the paper. As an aside, Stineman also proposes a rational interpolant you can use with the slope determination scheme in the linked paper; you can try that one instead if for some reason using a piecewise Hermite cubic is unsatisfactory.

share|improve this answer
    
How to determine the $y_i^{\prime}$ is shown by J. M. in another answer. –  Olathe Aug 20 '13 at 21:54
add comment

In general, no 2nd degree polynomial fits your requirements: If you fix its maximum/minimum at the highest/lowest of your three points, just one of the remaining two points would completely determine the curve due to its symmetry.

But if you want to use this to control volume, there are probably some additional side conditions that you need to consider anyway: If y2 is the highest point, you probably want the curve to have just one local maximum (at x2, then). I would also guess that the slope at x1 and x3 should be 0 (though that depends). In any case, you probably don't want a polynomial. The simplest solution might be to take pieces of sine curves between $0$ and $\pi$, stretch them according to your values, and attach them at x2. You could also use splines, but then you explicitly need to fix the slope at x2 to be 0.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.