2
$\begingroup$

Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y value for a given x value using the provided points as fix points for a piecewise linear interpolation.

Caveat: The x-axis is cyclic, so it wraps around at a certain known value.

I'm searching a neat algorithm (or way to write this down) which can do this interpolation, so take an x value on the cyclic x-axes and compute the y- value using piecewise linear interpolation.

Example: Given FIX_POINTS = [(10, 50), (90, 100)], and a "cyclic interval" (so the value at which the x axes wraps) of 100, the interpolation would lead to the following results:

  interpolation(10) = 50 # No interpolation necessary, directly on fix points
  interpolation(90) = 100 # Same

  interpolation(50) = 75 # Normal Interpolation
  interpolation(0) = 75 # Wrap around interpolation
  interpolation(1) = 72.5 # Same
  interpolation(99) = 77.5 # Same

I'm not too curious in the actual programming, I'm searching for a way to write this down nicely. Maybe there is even an existing implementation for this? I'm having troubles asking google for the lack of search terms.

I implemented it myself, but it got a lot of code, so I'm in search of something simpler: https://gist.github.com/theomega/9782be548fd452e1f1469757387b35e4 . This implementation also is far from optimal on the computational side (scanning over the array).

I'm not sure if this is the stack exchange for this. Feel free to point me in a different direction.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "using linear interpolation"? There are multiple possible interpretations. One interpretation is: fit a least-squares regression line through all the points, then use that for prediction. Another interpretation is: treat those points as defining a piecewise linear function, then use that for prediction. Perhaps there are other interpretations as well. What did you have in mind? Perhaps you could draw a picture? $\endgroup$ – D.W. Mar 9 at 20:12
  • $\begingroup$ Thanks, I tried to clarify the text, I was thinking of a piecewise linear interpolation. I'll also try to come up with a nice drawing. $\endgroup$ – theomega Mar 9 at 20:23
1
$\begingroup$

Find the fixed point $(x_l,y_l)$ just to the left of your $x$-value, and the fixed point $(x_r,y_r)$ just to the right of your $x$-value. Then use the line between those two fixed points to interpolate.

To find the fixed point to the left and the fixed point to the right, store the fixed points in sorted order (sorted by their $x$-coordinate). Then you can use binary search to find the fixed point to the left and to the right.

To deal with wrap-around, take the left-most fixed point and add a wrapped-around copy above the upper limit, and similarly add a copy of the right-most fixed point. For instance, suppose the limit is 0..100, and the left-most fixed point is $(5,20)$ and the right-most fixed point is $(98,3)$. Then you should add the two additional points $(105,20)$ and $(-2,3)$. Now apply the algorithm above.

$\endgroup$
  • $\begingroup$ That is an excellent idea, basically getting rid of the special case of the cyclicity by preprocessing. I implement this for fun here in python: gist.github.com/theomega/92ecec91461f0ea5de80acd27b624a6b. Works as expected (of course). I gonna leave the question open for some more days to see if someone finds an even better solution. $\endgroup$ – theomega Mar 9 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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