cyclic_interpolation_better.py

#!/usr/bin/env python

def get_fixpoint_before(fixpoints, x):
  """
    Find the fix point directly before the provided position.
  """
  assert len(fixpoints) > 0
  assert x >= 0

  return filter(lambda f: f[0] <= x, fixpoints)[-1]

def get_fixpoint_after(fixpoints, x):
  """
    Find the fix point directly after the provided position.
  """
  assert len(fixpoints) > 0
  assert x >= 0

  return filter(lambda f: f[0] >= x, fixpoints)[0]


def make_fixpoints_cyclic(fixpoints, cyclesize):
  """Adapts the fixpoints for the cyclic use-case, by doing the following:
    - Sort the fixpoints by x value
    - Copy the last fixpoint as first fixpoint
    - Copy the first fixpoint as the last fixpoint
  """

  # Sort fix points by x value
  fixpoints = sorted(fixpoints, key=lambda f: f[0])

  last_fixpoint = fixpoints[-1]
  first_fixpoint = fixpoints[0]
 
  return [
    ((cyclesize - last_fixpoint[0]) * -1, last_fixpoint[1])
  ] + fixpoints + [
    ((cyclesize + first_fixpoint[0]), first_fixpoint[1])
  ]

def interpolate_value(fixpoints, cyclesize, x):
  """
    Interpolates the value at the provided position. It uses the fixpoints provided
    for the interpolation and assumes that the x axis is from 0 till cyclesize-1
    inclusive.
  """
  assert len(fixpoints) > 0
  assert x >= 0
  assert x < cyclesize

  modified_fixpoints = make_fixpoints_cyclic(fixpoints, cyclesize)

  before = get_fixpoint_before(modified_fixpoints, x)
  after = get_fixpoint_after(modified_fixpoints, x)  

  # If we are directly on a fix point, return it
  # In this case before == after == x
  if x == before[0]:
    return before[1]

  # Compute Slope
  delta_x = after[0] - before[0]
  delta_y = after[1] - before[1]
  slope = float(delta_y) / float(delta_x)

  # Compute Increment
  increment = (x - before[0]) * slope

  return before[1] + increment

import unittest
import random 

# Circle runs from 0 to 99
TEST_CYCLE_SIZE = 100
# Format (x, y)
TEST_FIX_POINTS = [
  (5, 50),
  (25, 25),
  (30, 25),
  (40, 1025),
  (75, 525),
  (80, 30),
  (90, 100)
]

class TestHelpers(unittest.TestCase):
  def test_get_fixpoint_before(self):
    # If you are on a fix point, this point is taken
    for (p, v) in TEST_FIX_POINTS:
      self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, p), (p, v))

    self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, 15), (5, 50))
    self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, 24), (5, 50))
    self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, 34), (30, 25))
    self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, 83), (80, 30))
    self.assertEquals(get_fixpoint_before(TEST_FIX_POINTS, 92), (90, 100))

  def test_get_fixpoint_after(self):
    # If you are on a fix point, this point is taken
    for (p, v) in TEST_FIX_POINTS:
      self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, p), (p, v))

    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 1), (5, 50))
    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 6), (25, 25))
    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 24), (25, 25))
    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 34), (40, 1025))
    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 78), (80, 30))
    self.assertEquals(get_fixpoint_after(TEST_FIX_POINTS, 83), (90, 100))

  def test_make_fixpoints_cyclic(self):
    self.assertEquals(make_fixpoints_cyclic(TEST_FIX_POINTS, TEST_CYCLE_SIZE), [(-10, 100)] +
      TEST_FIX_POINTS + [(105, 50)])

  def test_make_fixpoints_cyclic_random(self):
    self.assertEquals(make_fixpoints_cyclic(random.sample(TEST_FIX_POINTS, len(TEST_FIX_POINTS)), TEST_CYCLE_SIZE), [(-10, 100)] +
      TEST_FIX_POINTS + [(105, 50)])


class TestCircleInterpolation(unittest.TestCase):
  def test_fixpoints(self):
    # All the fixpoints should return their values
    for (p, v) in TEST_FIX_POINTS:
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, p), v)

  def test_simple(self):
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 13), 40)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 22), 28.75)

      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 26), 25)       
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 29), 25)       

      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 31), 125)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 32), 225)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 38), 825)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 39), 925)

      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 55), 810.71, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 70), 596.428, 2)

      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 76), 426)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 77), 327)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 78), 228)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 79), 129)

      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 85), 65)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 88), 86)
      self.assertEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 89), 93)

  def test_wraparound(self):
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 91), 96.666, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 92), 93.333, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 93), 90, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 94), 86.666, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 95), 83.333, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 96), 80, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 97), 76.666, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 98), 73.333, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 99), 70, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 0), 66.666, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 1), 63.333, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 2), 60, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 3), 56.666, 2)
      self.assertAlmostEqual(interpolate_value(TEST_FIX_POINTS, TEST_CYCLE_SIZE, 4), 53.333, 2)

if __name__ == '__main__':
    unittest.main()