Interpolate on a cylic x axes

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.

• 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? – D.W. Mar 9 '19 at 20:12
• 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. – theomega Mar 9 '19 at 20:23

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.